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: 1.0 s

Memory Limit: 256.0 MB

Description

Mr. Heart, the enthusiastic explorer of numbers, he had an array A with N sizes, and he needed to find a special way to split this array.

Mr. Heart wanted to find how many ways he could divide the array into two parts where the XOR of the numbers in the first part equals the XOR of the numbers in the second part.

To solve this, Mr. Heart used a specific method:

• First part: Starts at index \(i\) and goes up to \({j-1}\).
• Second part: Starts at index \(j\) and goes up to \(k\).

He needed to find how many ways he could choose the indices \(i\), \(j\), and \(k\) (\({i < j ≤ k}\)) so that the XOR of the first part (\(A_i\) to \(A_{j-1}\)) is equal to the XOR of the second part (\(A_j\) to \(A_k\)).

Mr. Heart used his keen analytical skills to examine every possible split point, ensuring the XOR values of the two segments matched perfectly.

Mr. Heart now challenges you to solve this problem! Do you want to accept this challenge?

Input

The first Line contains an integer value \(T\) (1 ≤ T ≤ \(10^3\)), the number of test cases.
The second line contains an integer value \(N\) (2 ≤ N < \(2 * 10^5\)).
The third line contais \(N\) integers \(A_1\) , \(A_2\) ,,, \(A_N\) (1 ≤ \(A\) ≤ \(10 ^ {9}\))

Sum of \(N\) overall testcase doesn't exceed \(2 * 10^5\)

Output

Print the Number of ways which satisfying the condition.

Sample

1
4
4 5 4 5

3

In the sample test case, three ways are satisfying the condition, these are
If i = 1, j = 2, and k = 4, then it will satisfy the condition, since 4 = 5 ⊕ 4 ⊕ 5
If i = 1, j = 3, and k = 4, then it will satisfy the condition. since 4 ⊕ 5 = 4 ⊕ 5
If i = 1, j = 4, and k = 4, then it will satisfy the condition. since 4 ⊕ 5 ⊕ 4 = 5