题目描述

给定两个非负整数数组 $A=[a_1, a_2, \ldots, a_n]$ 和 $B=[b_1, b_2, \ldots, b_m]$。

定义 $S(i) = \{j | (a_i \oplus b_j) \leq x\}$。换句话说，$S(i)$ 是数组 $B$ 中所有满足 $a_i$ 与 $b_j$ 的按位异或结果不超过 $x$ 的下标 $j$ 的集合。

请求出最小的数字 $k$，使得可以将数组 $A$ 中的元素染成 $k$ 种颜色，且满足：如果 $S(x)$ 与 $S(y)$ 相交，则 $x$ 和 $y$ 必须被染成不同的颜色。

换言之，需要找到 $c_1, c_2, \ldots, c_n$，使得 $1 \le c_i \le k$，并且如果 $S(x) \cap S(y) \neq \varnothing$，则 $c_x \neq c_y$。

提醒一下，两个非负整数的按位“异或”（$\oplus$，xor）定义如下：将两个数写作二进制形式，结果的第 $i$ 个二进制位为 1，当且仅当两个参数中恰好有一个在该位为 1。例如，$(14 \text{ xor } 7) = (1110_2 \oplus 0111_2) = 1001_2 = 9$。该操作在所有现代编程语言中都有实现，在 C++、Java 和 Python 中写作 ^，在 Pascal 中写作 xor。

输入格式

此题的输入包含多个测试用例。

输入的第一行包含一个整数 $t$ $(1 \le t \le 100)$ —— 测试用例的数量。

接下来是各个测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $x$（$1 \le n, m \le 500\,000$，$0 \leq x < 2^{30}$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ —— 数组 $A$ 的元素（$0 \le a_i < 2^{30}$）。

第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$ —— 数组 $B$ 的元素（$0 \le b_i < 2^{30}$）。

保证所有测试用例的 $n$ 值之和以及 $m$ 值之和均不超过 $500\,000$。

输出格式

对于每个测试用例，输出一个整数 —— 所求的最小 $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

提示

评分规则