GCD vs. XOR
Optimizing is fun! Especially when it's not exactly required.
Everyone knows that bit operations (e.g. bitwise XOR) are faster than recursive functions (such as the greatest common divisor, GCD). To impress your internship supervisors you replaced, in the company's flagship project, all instances of gcd(x, y) with much quicker xor(x, y).
That was yesterday, on Friday. Now you start thinking whether you should have tested your new code beforedeploying to production... Well, better late than never. Given a sequence of numbers a[1], ..., a[n], determine how many pairs (i, j) (1 ≤ i < j ≤ n) actually satisfy gcd(a[i], a[j]) = xor(a[i], a[j]). Recall that gcd(x, y) denotes the greatest common divisor of x and y, while xor(x, y) is the bitwise-XOR operation on x and y.
Input
The first line contains the number of test cases z (1 ≤ z ≤ 20). The descriptions of the test cases follow.
The first line of a test case contains an integer n (1 ≤ n ≤ 2 000 000). The second line contains integers a[1], a[2], ..., a[n], all positive and not exceeding 10^6.
The total length of all sequences over all test cases does not exceed 3 * 10^7.
Output
For each test case output a single integer: the number of pairs (a[i], a[j]) with i < j satisfying gcd(a[i], a[j]) = xor(a[i], a[j]).