Chef has two arrays A and B, each of length N.
A pair (i,j) (1≤i<j≤N) is said to be a good pair if and only if
Here, ⊕ denotes the bitwise XOR operation.
Determine the number of good pairs.
- The first line of input will contain a single integer T, denoting the number of test cases. The description of the test cases follows.
- Each test case consists of three lines of input:
- The first line contains a single integer N — the size of the arrays A and B.
- The second line contains N space-separated integers A1,A2,…,AN — the elements of array A.
- The third line contains N space-separated integers B1,B2,…,BN — the elements of array B.
- For each test case, output on a new line the number of good pairs.
- The sum of N over all test cases does not exceed 3⋅105
2 4 1 2 3 4 4 3 2 1 5 1 3 4 7 9 5 1 0 5 13
Test Case 1: There are 2 good pairs: (1,4) and (2,3). This is because A1⊕A4=1⊕4=B1⊕B4, and A2⊕A3=2⊕3=B2⊕B3.
Test Case 2: The 4 good pairs are (1,3), (2,4), (1,5) and (3,5). For example, (2,4) is good because A2⊕A4=3⊕7=4 and B2⊕B4=1⊕5=4.