優化很有趣！特別是在不一定需要優化的時候。

大家都知道位元運算（例如位元 XOR）比遞迴函式（例如最大公因數，GCD）更快。為了給你的實習主管留下深刻印象，你在公司的旗艦專案中，將所有 $gcd(x, y)$ 的實例都替換成了速度快得多的 $xor(x, y)$。

那是昨天，星期五的事。現在你開始思考，在部署到生產環境之前，是否應該先測試一下你的新程式碼……好吧，亡羊補牢，猶未晚矣。給定一個數列 $a_1, \dots, a_n$，請計算有多少對 $(i, j)$ ($1 \le i < j \le n$) 實際上滿足 $gcd(a_i, a_j) = xor(a_i, a_j)$。回想一下，$gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公因數，而 $xor(x, y)$ 是 $x$ 和 $y$ 的位元 XOR 運算。

輸入格式

輸入的第一行包含測試案例的數量 $z$ ($1 \le z \le 20$)。接著是各個測試案例的描述。 每個測試案例的第一行包含一個整數 $n$ ($1 \le n \le 2\,000\,000$)。第二行包含整數 $a_1, a_2, \dots, a_n$，所有整數皆為正整數且不超過 $1\,000\,000$。 所有測試案例中數列的總長度不超過 $3 \cdot 10^7$。

輸出格式

對於每個測試案例，輸出一個整數：滿足 $gcd(a_i, a_j) = xor(a_i, a_j)$ 且 $i < j$ 的數對 $(i, j)$ 的數量。

範例

輸入 1

1
4
2 3 4 3

輸出 1

2