Given an array A and target value, find the number of subarrays whose XOR is equal to the target value.

Example

A: [1, 2, 3, 4]
Target: 3
Subarrays: [
 [3],
 [1, 2]
]
Number of subarrays: 2

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input has three lines:

• An integer ‘n’ denoting the length of the array A.
• n space-separated integers denoting the elements of the array A.
• The target value.

Output Format

For each test case, the output has one line with the number of possible subarrays.

Sample Input

2
4
1 4 1 4
5
6
2 4 3 6 7 9
6

Expected Output

3
3

Constraints

1 <= T <= 10
1 <= n <= 105
1 <= Ai <= 109
1 <= target <= 109