Problem Description

Given two non-negative integer arrays $A=[a_1, a_2, \ldots, a_n]$ and $B=[b_1, b_2, \ldots, b_m]$.

Define $S(i) = \{j | (a_i \oplus b_j) \leq x\}$. In other words, $S(i)$ is the set of indices $j$ in array $B$ such that the bitwise XOR of $a_i$ and $b_j$ is at most $x$.

Find the minimum number $k$ such that the elements in array $A$ can be colored using $k$ colors, and the following condition holds: if $S(x)$ and $S(y)$ intersect, then $x$ and $y$ must be colored with different colors.

That is, you need to find $c_1, c_2, \ldots, c_n$ such that $1 \le c_i \le k$, and if $S(x) \cap S(y) \neq \varnothing$, then $c_x \neq c_y$.

As a reminder, the bitwise XOR ($\oplus$, xor) of two non-negative integers is defined as follows: write both numbers in binary, and the $i$-th bit of the result is 1 if and only if exactly one of the two numbers has a 1 in that bit. For example, $(14 \text{ xor } 7) = (1110_2 \oplus 0111_2) = 1001_2 = 9$. This operation is implemented in all modern programming languages: it is written as ^ in C++, Java, and Python, and as xor in Pascal.

Input Format

The input contains multiple test cases.

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

The following lines describe the test cases.

The first line of each test case contains three integers $n$, $m$, and $x$ ($1 \le n, m \le 500\,000$, $0 \leq 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 the sum of $n$ over all test cases and the sum of $m$ over all test cases are both at most $500\,000$.

Output Format

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

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

1
4
5

Hint

Scoring Rules

Translated by ChatGPT 5