You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

On the starship Aurora, maintaining a stable warp drive requires precise calibration of onboard sensors. The ship’s chief engineer has deployed \(N\) sensors in slots numbered from \(1\) to \(N\). Each sensor \(i\) has a signal strength represented by an integer \(A_i\).

To ensure safe warp calibration, the engineers must evaluate pairs of sensors \((i, j)\) such that \(1 ≤ i < j ≤ N\). A pair is considered good if it satisfies the following condition:

• \((i ⊕ A_i) < ((i ⊕ A_j) ⊕ j)\)

Where ⊕ denotes the bitwise XOR operation.
Your task is to determine the number of good pairs among the sensors.

Input

The input begins with an integer  T, representing the number of test cases. For each test case, the first line contains an integer  N, the number of sensors. The second line contains  N  space-separated integers  \(A_1, A_2, ..., A_N\), representing the signal strengths of the sensors.

• T — number of test cases (\(1 ≤ T ≤ 1000\))
• N — number of sensors (\(1 ≤ N ≤ 3 * 10^5\))
• N space-separated integers \(A_1, A_2, ..., A_N\) — the sensor readings (\(1 ≤ A_i ≤ 10^9\))

It is guaranteed that the sum of N over all test cases does not exceed \(3 * 10^5\).

Output

For each test case, output a single line containing one integer: the number of good pairs that satisfy the condition above.

Sample

2
5
6 5 6 1 6 
6
5 3 8 3 3 9 

2
11