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 ((Ai⊕Aj)((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.

Output Format

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

• 1≤T≤101≤T≤10
• 1≤N≤1051≤N≤105
• 0≤Ai,X≤1090≤Ai,X≤109

Sample Input 1 

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

Sample Output 1

Chef Find XOR Beautiful solution codechef

10
9

Explanation

Test case 11: There are 1010 pairs of (i,j)(i,j) (1≤i,j≤N)(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) (1≤i,j≤N)(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).

ANSWER

“Click Here“