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 before deploying to production... Well, better late than never. Given a sequence of numbers a1, ..., an, determine how many pairs (i, j) (1 ≤ i < j ≤ n) actually satisfy gcd(ai, aj) = xor(ai, aj). 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 a1, a2, ..., an, all positive and not exceeding 106.

The total length of all sequences over all test cases does not exceed 3 * 107.

Output

For each test case output a single integer: the number of pairs (ai, aj) with i < j satisfying gcd(ai, aj) = xor(ai, aj).