Chef and his friends would like to attend a large New Year's party in Goa. However, their teacher has given them an assignment to complete. Chef asked for your help to complete the assignment quickly so that he can attend the party with complete freedom.

Chef was given an array $A = [A_{1}, A_{2}, \ldots, A_{N}]$ of length $N, an array B = [B_{1}, B_{2}, \ldots, B_{M}]$ of length M, and a prime number P. His task is to find the number of good pairs. An ordered pair of integers (i, j) is said to be a good pair if it satisfies the following conditions:
1 ≤ i ≤ N
1 ≤ j ≤ M
$(A_{i} \oplus B_{j}) < P$
$P divides ((A_{i} \cdot (A_{i} \oplus B_{j})) - 1)$

where $\oplus$ denotes the [bitwise XOR] operation.

Please help Chef and his friends, and find the number of good pairs.

------ Input Format ------

• The first line of 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 three space-separated integers N, M, and P, respectively.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \ldots, A_{N}$.
• The third line of each test case contains $M space-separated integers B_{1}, B_{2}, \ldots, B_{M}$.

------ Output Format ------

For each test case, output one line containing a single integer — the number of good pairs.

------ Constraints ------

$1 ≤ T ≤ 10^{3}$
$1 ≤ N, M ≤ 2 \cdot 10^{5}$
$2 ≤ A_{i}, B_{j} ≤ 10^{9}$ for every $1≤ i ≤ N$ and $1≤ j ≤ M$
$2 ≤ P ≤ 10^{9}$
$P$ is a prime number
- Sum of $N$ across all test cases will not exceed $2 \cdot 10^{5}$
- Sum of $M$ across all test cases will not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------
3
2 2 17
7 14
2 13
1 1 11
2
2
4 3 101
10 91 99 200
81 182 149
----- Sample Output 1 ------
1
0
3

----- explanation 1 ------
Test Case $1$: There are $4$ ordered pairs of indices. Looking at them individually,
- $(1,1)$ is a good pair because $(7\oplus 2) = 5 < 17$, and $((7 \cdot (7 \oplus 2)) - 1) = 34$ is divisible by $17$.
- $(1, 2)$ is not a good pair because $((7 \cdot (7 \oplus 13)) - 1) = 69$ is not divisible by $17$.
- $(2, 1)$ is not a good pair because $((14 \cdot (14 \oplus 2)) - 1) = 167$ is not divisible by $17$.
- $(2, 2)$ is not a good pair because $((14 \cdot (14 \oplus 13)) - 1) = 41$ is not divisible by $17$.

Test Case $2$: The only ordered pair of indices is $(1, 1)$. This is not a good pair because $((2 \cdot (2 \oplus 2)) - 1) = -1$ is not divisible by $11$, since it leaves a remainder of $10$.

见题面

见题面