题目描述

小 A 在进行特殊的魔法实验，她有 $n$ 种材料，每种材料有一个权值 $a_i$，权值之间互不相同。每次她会选择一对材料组合起来释放一个美观度为 $a_i \oplus a_j$ 的魔法。

定义一个魔法价值是其美观度在 $10$ 进制表示下的位数，小 A 想要知道，她能释放的 $\frac{n(n-1)}{2}$ 个魔法的价值之和。

注：本题中 $\oplus$ 是按位异或的符号。

输入格式

第一行一个正整数 $n$；

接下来一行 $n$ 个整数表示 $a_i$。

输出格式

一个正整数，表示答案。

样例

input

3
1 10 30

output

6

数据范围与提示

对于 $30\%$ 的数据满足 $n\le 1000$；

对于 $50\%$ 的数据满足 $n\le 3000$；

对于 $70\%$ 的数据满足 $a_i\le 10^7$；

对于 $100\%$ 的数据满足 $n\le 5\times 10^4,0\le a_i\le 10^{18}$。