题目描述

江月诗拿到了一个由 $n$ 个整数构成的数组 $\{ a_1, a_2, \dots , a_n \}$ 他想知道，从中任取两个元素 $a_i$ 和 $a_j$ $(i< j)$，满足 $a_i$ $XOR$ $a_j$ $=$ $gcd(a_i, a_j)$ 的方案数是多少？

$gcd$，即最大公约数，指两个整数共有约束中最大的一个。例如，$12$ 和 $30$ 的公约数有 $1,2,3,6$，其中最大的约数是 $6$，因此 $gcd(12,30)=6$。

其中，$XOR$ 表示按位异或运算。如果您需要更多位运算相关知识，可以参考 位运算 - OI Wiki。

输入格式

第一行输入一个正整数 $n$ $(1\leq n \leq 2\times 10^{5})$ 代表数组中元素数量。

第二行输入 $n$ 个正整数 ${a_1, a_2, \dots , a_n}$ $(1 \leq a_i \leq 2 \times 10^5)$。

输出格式

输出一个整数，代表选取两个元素的异或等于最大公约数的方案数。

输入样例

5
2 6 2 3 4

输出样例

3

说明/提示

在这个样例中，选取第 $1,4$ 个元素、第 $3,4$ 个元素、第 $2,5$ 个元素，均满足条件。