Read problems statements [Hindi] ,[Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

Chef is stuck at the following problem. Help him solve it!

Chef has a sequence of integers $A_{1}, A_{2}, \dots, A_{N}$. He should find the number of pairs $(i, j)$ such that $1 ≤ i < j ≤ N$ and the bitwise XOR of $A_{i}$ and $A_{j}$ can be written as a sum of two (not necessarily different) prime numbers with the same parity (both odd or both even).

------ Input ------
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 second line contains $N$ space-seprated integers $A_{1}, A_{2}, \dots, A_{N}$.

------ Output ------
For each test case, print a single line containing one integer — the number of valid pairs.

------ Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$ for each valid $i$

------ Subtasks ------
Subtask #1 (10 points): $1 ≤ N ≤ 10^{3}$

Subtask #2 (90 points): original constraints

----- Sample Input 1 ------
1
5
2 4 8 1 3
----- Sample Output 1 ------
3
----- explanation 1 ------
Example case 1: The three valid pairs are $(1, 2)$, $(1, 3)$ and $(2, 3)$. For example, $A_{1} \oplus A_{2} = 2 \oplus 4 = 6 = 3+3$.

见题面

见题面