# [Coding] Chef Find XOR Beautiful solution codechef

## Chef Find XOR Beautiful solution codechef

You are given an array AA of size NN and an integer XX.

Find the count of all the pairs (i,j)(i,j) such that ((AiAj)((Ai⊕Aj) && X)=0X)=0. Here  and && denote bitwise XOR and bitwise AND operations respectively.

### Input Format

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN – the size of the array.
• The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN – the elements of the array.
• The third line of each test case contains a single integer XX.

## Chef Find XOR Beautiful solution codechef

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

### Constraints

• 1T101≤T≤10
• 1N1051≤N≤105
• 0Ai,X1090≤Ai,X≤109

### Sample Input 1

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


## Chef Find XOR Beautiful solution codechef

10
9


### Explanation

Test case 11: There are 1010 pairs of (i,j)(i,j) (1i,jN)(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),(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 22: There are 99 pairs of (i,j)(i,j) (1i,jN)(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),(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2), and (3,3)(3,3).