Optymalizacja to świetna zabawa! Zwłaszcza wtedy, gdy nie jest ona konieczna.

Wszyscy wiedzą, że operacje bitowe (np. bitowe XOR) są szybsze niż funkcje rekurencyjne (takie jak największy wspólny dzielnik, GCD). Aby zaimponować swoim przełożonym na stażu, zastąpiłeś w flagowym projekcie firmy wszystkie wystąpienia $gcd(x, y)$ znacznie szybszymi $xor(x, y)$.

To było wczoraj, w piątek. Teraz zastanawiasz się, czy nie powinieneś był przetestować swojego nowego kodu przed wdrożeniem na produkcję... Cóż, lepiej późno niż wcale. Mając dany ciąg liczb $a_1, \dots, a_n$, określ, ile par $(i, j)$ ($1 \le i < j \le n$) faktycznie spełnia warunek $gcd(a_i, a_j) = xor(a_i, a_j)$. Przypomnijmy, że $gcd(x, y)$ oznacza największy wspólny dzielnik $x$ i $y$, podczas gdy $xor(x, y)$ to operacja bitowego XOR na $x$ i $y$.

Wejście

Pierwsza linia wejścia zawiera liczbę zestawów danych $z$ ($1 \le z \le 20$). Następnie następują opisy zestawów danych.

Pierwsza linia zestawu danych zawiera liczbę całkowitą $n$ ($1 \le n \le 2\,000\,000$). Druga linia zawiera liczby całkowite $a_1, a_2, \dots, a_n$, wszystkie dodatnie i nieprzekraczające $1\,000\,000$.

Całkowita długość wszystkich ciągów we wszystkich zestawach danych nie przekracza $3 \cdot 10^7$.

Wyjście

Dla każdego zestawu danych wypisz pojedynczą liczbę całkowitą: liczbę par $(a_i, a_j)$ z $i < j$ spełniających $gcd(a_i, a_j) = xor(a_i, a_j)$.

Przykład

Wejście 1

1
4
2 3 4 3

Wyjście 1

2