## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Chef Find XOR Beautiful Solution | CodeChef Problem Solution 2022

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

Find the count of all the pairs $\left(i,j\right)$ such that $\left(\left({A}_{i}\oplus {A}_{j}\right)$ $\mathrm{&}$ $X\right)=0$. Here $\oplus$ and $\mathrm{&}$ 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},\dots ,{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\le T\le 10$
• $1\le N\le {10}^{5}$
• $0\le {A}_{i},X\le {10}^{9}$

### Sample Input 1

2
4
1 2 3 1
1
3
0 0 0
21


### Sample Output 1

10
9


### Explanation

Test case $1$: There are $10$ pairs of $\left(i,j\right)$ $\left(1\le i,j\le N\right)$ satisfying the condition. These pairs are: $\left(1,1\right),\left(1,3\right),\left(1,4\right),\left(2,2\right),\left(3,1\right),\left(3,3\right),\left(3,4\right),\left(4,1\right),\left(4,3\right),$ and $\left(4,4\right)$.

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