GCD와 XOR

최적화는 즐겁다. 특히 꼭 필요하지 않을 때 더 즐겁다.

비트 연산(예: 비트별 XOR)이 재귀 함수(예: 최대공약수, GCD)보다 빠르다는 것은 모두가 안다. 인턴 지도 담당자에게 좋은 인상을 주려고, 회사 주력 프로젝트에 있던 모든 $\mathop{gcd}(x,y)$를 훨씬 빠른 $\mathop{xor}(x,y)$로 바꿨다.

그 일은 어제 금요일에 있었다. 이제 새 코드를 운영 환경에 배포하기 전에 테스트했어야 했는지 고민하고 있다. 늦었지만 안 하는 것보다는 낫다. 수열 $a_1, \ldots, a_n$이 주어질 때, 실제로 $\mathop{gcd}(a_i, a_j) = \mathop{xor}(a_i, a_j)$를 만족하는 쌍 $(i, j)$ ($1 \leq i < j \leq n$)의 개수를 구하라. 여기서 $\mathop{gcd}(x,y)$는 $x$와 $y$의 최대공약수를, $\mathop{xor}(x,y)$는 $x$와 $y$의 비트별 XOR 연산 결과를 뜻한다.

입력의 첫 줄에는 테스트 케이스의 개수 $z$ ($1 \leq z \leq 20$)가 주어진다. 이어서 테스트 케이스가 차례로 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $n$ ($1 \leq n \leq 2\,000\,000$)이 주어진다. 둘째 줄에는 모두 양수이며 1,000,000을 넘지 않는 정수 $a_1, a_2, \ldots, a_n$이 주어진다.

모든 테스트 케이스의 수열 길이 합은 $3 \cdot 10^7$을 넘지 않는다.

각 테스트 케이스마다 $i < j$이고 $\mathop{gcd}(a_i, a_j) = \mathop{xor}(a_i, a_j)$를 만족하는 쌍 $(a_i, a_j)$의 개수를 한 줄에 정수 하나로 출력한다.