Counting Pairs

Consider the binary operator $\oplus_b(x, y)$ that is defined for $b \in \{2, 4\}$ as follows. First, convert both $x$ and $y$ into base $b$. Then, for each corresponding digit pair, the resulting digit can be calculated by adding the digit pair modulo $b$. Finally, convert the result back to base ten. Notice that $\oplus_2$ is the bitwise XOR operator.

For instance, $\oplus_4(18, 7) = 21$ can be calculated as follows. The base four representations of $18$ and $7$ are $(102)_4$ and $(013)_4$, respectively. After the addition for each digit pair, the result is $(111)_4$, or $21$ in base ten.

You are given a list of $N$ integers, $A_1, A_2, \dots , A_N$.

Determine the number of pairs $(i, j)$ such that $1 ≤ i < j ≤ N$ and $\oplus_2(A_i , A_j ) = \oplus_4(A_i , A_j )$.

The first line consists of an integer $N$ ($2 ≤ N ≤ 200\, 000$).

The next line consists of $N$ integers $A_i$ ($0 ≤ A_i ≤ 10^{12}$).

Output a single integer representing the number of pairs $(i, j)$ such that $1 ≤ i < j ≤ N$ and $\oplus_2(A_i , A_j ) = \oplus_4(A_i , A_j )$.