K. Suminusor
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a_1, a_2, \ldots, a_n$$$ and an integer $$$k$$$.

For every subarray $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$), define $$$$$$ f(l,r)=\left[\sum_{i=l}^{r-1} a_i \oplus a_{i+1}\right]-a_l \oplus a_r $$$$$$ Here $$$\oplus$$$ denotes the bitwise XOR operation. If $$$l=r$$$, the sum is empty and is defined to be $$$0$$$.

Count the number of subarrays $$$[l,r]$$$ such that $$$f(l,r)=k$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le k \lt 2^{30}$$$) — the length of the array and the required value of $$$f(l,r)$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt 2^{30}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print one integer — the number of subarrays $$$[l,r]$$$ for which $$$f(l,r)=k$$$.

Example
Input
6
1 0
7
3 0
1 2 3
3 2
1 2 3
4 6
0 3 5 6
5 1
0 1 0 1 0
4 4
0 3 0 3
Output
1
5
1
1
0
0
Note

In the first test case, the only subarray is $$$[1,1]$$$. Both the empty sum and $$$a_1 \oplus a_1$$$ are zero, so its value is zero.

In the second test case, all three subarrays of length one and both subarrays of length two have value zero. The subarray $$$[1,3]$$$ has value $$$$$$ (1 \oplus 2)+(2 \oplus 3)-(1 \oplus 3)=3+1-2=2. $$$$$$ Therefore, the answer is $$$5$$$.