You are given an array A of size N and an integer X.

Find the count of all the pairs (i,j) such that $((A_{i} \oplus A_{j})$ \& $X) = 0. Here \oplus$ and \& denote [bitwise XOR] and [bitwise AND] operations respectively..

------ Input Format ------

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer N - the size of the array.
• The second line contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N} -$ the elements of the array.
• The third line of each test case contains a single integer X.

------ Output Format ------

For each test case, print a single line containing one integer ― the total number of pairs satisfying the condition.

------ Constraints ------

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i}, X ≤ 10^{9}$

----- Sample Input 1 ------
2
4
1 2 3 1
1
3
0 0 0
21
----- Sample Output 1 ------
10
9
----- explanation 1 ------
Test case $1$: There are $10$ pairs of $(i,j)$ $(1≤ i,j ≤ N)$ satisfying the condition. These pairs are: $(1,1),(1,3),(1,4),(2,2),(3,1),(3,3),(3,4),(4,1),(4,3),$ and $(4,4)$.

Test case $2$: There are $9$ pairs of $(i,j)$ $(1≤ i,j ≤ N)$ satisfying the condition. These pairs are: $(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),$ and $(3,3)$.

见题面

见题面