题目描述

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

输入描述

第一行输入一个正整数 $n \left(1 \leq n \leq 2 \times 10^5\right)$ 代表数组中的元素数量。
第二行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$$\left(1 \leq a_i \leq 2 \times 10^5\right)$ 代表数组中的元素。

输出描述

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

样例1

输入

5
2 6 2 3 4

输出

3

说明

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