Two arrays of non-negative integers are given: $A = [a_1, a_2, \ldots, a_n]$ and $B = [b_1, b_2, \ldots, b_m]$.

Let $S(i) = \{\, j \mid (a_i \oplus b_j) \le x \,\}$. In other words, $S(i)$ is the set of all indices $j$ of array $B$ such that the bitwise exclusive OR of $a_i$ and $b_j$ does not exceed $x$.

It is required to find the minimum number $k$ such that it is possible to color the elements of array $A$ with $k$ colors in such a way that if $S(x)$ and $S(y)$ intersect, then $x$ and $y$ are colored with different colors.

In other words, it is possible to find $c_1, c_2, \ldots, c_n$ such that $1 \le c_i \le k$, and if $S(x) \cap S(y) \ne \varnothing$, then $c_x \ne c_y$.

Recall that the bitwise “exclusive OR” ($\oplus$, xor) of two non-negative integers is defined as follows: write both numbers in binary representation; the $i$-th binary digit of the result is equal to $1$ if and only if exactly one of the arguments has $1$ in this position. For example, $(14 \oplus 7) = (1110_2 \oplus 0111_2) = 1001_2 = 9$. This operation is implemented in all modern programming languages; in C++, Java, and Python it is written as ^, and in Pascal as xor.

Input Format

The input data for this problem contains several test cases.

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

Descriptions of the test cases follow.

In the first line of each test case, three integers $n$, $m$, and $x$ are given ($1 \le n, m \le 500\,000$, $0 \le x < 2^{30}$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ — the elements of array $A$ ($0 \le a_i < 2^{30}$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ — the elements of array $B$ ($0 \le b_i < 2^{30}$).

It is guaranteed that both the sum of all values $n$ and the sum of all values $m$ over all test cases do not exceed $500\,000$.

Output Format

For each test case, output one integer — the minimum required value $k$.

Scoring

Example

standard input

3
2 2 0
0 0
1 1
5 5 3
0 1 2 3 4
0 1 2 3 4
5 5 4
0 1 2 3 4
0 1 2 3 4

standard output

1
4
5