L'optimisation est amusante ! Surtout quand elle n'est pas strictement nécessaire.

Tout le monde sait que les opérations sur les bits (par exemple, le XOR bit à bit) sont plus rapides que les fonctions récursives (telles que le plus grand commun diviseur, GCD). Pour impressionner vos superviseurs de stage, vous avez remplacé, dans le projet phare de l'entreprise, toutes les instances de $gcd(x, y)$ par le beaucoup plus rapide $xor(x, y)$.

C'était hier, vendredi. Maintenant, vous commencez à vous demander si vous auriez dû tester votre nouveau code avant de le déployer en production... Eh bien, mieux vaut tard que jamais. Étant donné une séquence de nombres $a_1, \dots, a_n$, déterminez combien de paires $(i, j)$ ($1 \le i < j \le n$) satisfont réellement $gcd(a_i, a_j) = xor(a_i, a_j)$. Rappelez-vous que $gcd(x, y)$ désigne le plus grand commun diviseur de $x$ et $y$, tandis que $xor(x, y)$ est l'opération XOR bit à bit sur $x$ et $y$.

Entrée

La première ligne de l'entrée contient le nombre de cas de test $z$ ($1 \le z \le 20$). Les descriptions des cas de test suivent.

La première ligne d'un cas de test contient un entier $n$ ($1 \le n \le 2\,000\,000$). La deuxième ligne contient les entiers $a_1, a_2, \dots, a_n$, tous positifs et ne dépassant pas $1\,000\,000$.

La longueur totale de toutes les séquences sur l'ensemble des cas de test ne dépasse pas $3 \cdot 10^7$.

Sortie

Pour chaque cas de test, affichez un seul entier : le nombre de paires $(a_i, a_j)$ avec $i < j$ satisfaisant $gcd(a_i, a_j) = xor(a_i, a_j)$.

Exemples

Entrée 1

1
4
2 3 4 3

Sortie 1

2