Chef Find XOR Beautiful Solution | CodeChef Problem Solution 2022

Chef Find XOR Beautiful Solution | CodeChef Problem Solution 2022

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

Find the count of all the pairs (i,j)$(i,j)$ such that ((Ai⊕Aj)$((A_i\oplus A_j)$ &$\mathrm{\&}$ X)=0$X)=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$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$ - the size of the array.
• The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ - the elements of the array.
• The third line of each test case contains a single integer X$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\le T\le 10$
• 1≤N≤105$1\le N\le {10}^5$
• 0≤Ai,X≤109$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$1$: There are 10$10$ pairs of (i,j)$(i,j)$ (1≤i,j≤N)$(1\le i,j\le 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),$(1,1),(1,3),(1,4),(2,2),(3,1),(3,3),(3,4),(4,1),(4,3),$ and (4,4)$(4,4)$.

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