最適化は楽しいものです！特に、それが必ずしも必要でない場合はなおさらです。

誰もが知っているように、ビット演算（例えばビットごとのXOR）は、再帰的な関数（最大公約数、GCDなど）よりも高速です。インターンシップの指導教官を感心させるために、あなたは会社の主力プロジェクトにおいて、すべての $gcd(x, y)$ を、より高速な $xor(x, y)$ に置き換えました。

それは昨日の金曜日のことでした。今、あなたは本番環境にデプロイする前に新しいコードをテストすべきだったのではないかと考え始めています……まあ、遅すぎることなどありません。数列 $a_1, \dots, a_n$ が与えられたとき、$i < j$ を満たす組 $(i, j)$ のうち、$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$) が含まれます。2行目には整数 $a_1, a_2, \dots, a_n$ が含まれます。これらはすべて正の整数であり、$1\,000\,000$ を超えません。

すべてのテストケースにおける数列の長さの合計は $3 \cdot 10^7$ を超えません。

出力

各テストケースについて、$i < j$ かつ $gcd(a_i, a_j) = xor(a_i, a_j)$ を満たす組 $(a_i, a_j)$ の数を単一の整数として出力してください。

入出力例

入力 1

1
4
2 3 4 3

出力 1

2