War of XORs

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 \le i \lt j \le 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