¡Optimizar es divertido! Especialmente cuando no es estrictamente necesario.

Todo el mundo sabe que las operaciones a nivel de bits (por ejemplo, XOR a nivel de bits) son más rápidas que las funciones recursivas (como el máximo común divisor, GCD). Para impresionar a tus supervisores de prácticas, reemplazaste en el proyecto insignia de la empresa todas las instancias de $gcd(x, y)$ con la mucho más rápida $xor(x, y)$.

Eso fue ayer, viernes. Ahora empiezas a pensar si deberías haber probado tu nuevo código antes de desplegarlo en producción... Bueno, más vale tarde que nunca. Dada una secuencia de números $a_1, \dots, a_n$, determina cuántos pares $(i, j)$ ($1 \le i < j \le n$) satisfacen realmente $gcd(a_i, a_j) = xor(a_i, a_j)$. Recuerda que $gcd(x, y)$ denota el máximo común divisor de $x$ e $y$, mientras que $xor(x, y)$ es la operación XOR a nivel de bits entre $x$ e $y$.

Entrada

La primera línea de la entrada contiene el número de casos de prueba $z$ ($1 \le z \le 20$). A continuación siguen las descripciones de los casos de prueba.

La primera línea de un caso de prueba contiene un entero $n$ ($1 \le n \le 2\,000\,000$). La segunda línea contiene los enteros $a_1, a_2, \dots, a_n$, todos positivos y que no exceden $1\,000\,000$.

La longitud total de todas las secuencias en todos los casos de prueba no excede $3 \cdot 10^7$.

Salida

Para cada caso de prueba, imprime un único entero: el número de pares $(i, j)$ con $i < j$ que satisfacen $gcd(a_i, a_j) = xor(a_i, a_j)$.

Ejemplos

Entrada 1

1
4
2 3 4 3

Salida 1

2