최적화는 즐거운 일입니다! 특히 반드시 필요한 경우가 아닐 때는 더욱 그렇습니다.

모두가 비트 연산(예: 비트 XOR)이 재귀 함수(예: 최대공약수, GCD)보다 빠르다는 것을 알고 있습니다. 인턴십 감독관에게 깊은 인상을 남기기 위해, 당신은 회사의 주력 프로젝트에 있는 모든 $gcd(x, y)$ 호출을 훨씬 빠른 $xor(x, y)$로 교체했습니다.

지난 금요일의 일이었습니다. 이제 당신은 프로덕션 환경에 배포하기 전에 새로운 코드를 테스트했어야 했는지 고민하기 시작합니다... 뭐, 늦었다고 생각할 때가 가장 빠른 법이죠. 수열 $a_1, \dots, a_n$이 주어졌을 때, $gcd(a_i, a_j) = xor(a_i, a_j)$를 만족하는 쌍 $(i, j)$ ($1 \le i < j \le n$)가 몇 개인지 구하세요. 여기서 $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$)이 주어집니다. 두 번째 줄에는 $1$ 이상 $1\,000\,000$ 이하의 양의 정수 $a_1, a_2, \dots, a_n$이 주어집니다.

모든 테스트 케이스에 대한 수열 길이의 총합은 $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