[AdditionalFile5571.zip](file://AdditionalFile5571.zip?type=additional_file)

#5571. 「ROIR 2026 Day2」XOR 着色

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 ROI Regional 2026 Day2 T4. XOR Раскраска

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

对于数组 $A$ 中的每个元素 $a_i$，定义集合 $S(i) = \{ j \mid (a_i \oplus b_j) \leq x \}$，即数组 $B$ 中所有满足 $a_i$ 与 $b_j$ 的按位异或不超过 $x$ 的下标 $j$ 的集合。

要求找到最小的整数 $k$，使得能够用 $k$ 种颜色给数组 $A$ 的 $n$ 个元素着色，满足：

如果两个集合 $S(p)$ 和 $S(q)$ 有非空交集（$S(p) \cap S(q) \neq \varnothing$），则元素 $p$ 和 $q$ 必须着不同颜色。

换句话说，构造着色方案 $c_1, c_2, \dots, c_n$ $(1 \leq c_i \leq k)$，使得当 $S(p) \cap S(q) \neq \varnothing$ 时有 $c_p \neq c_q$。

按位异或（$\oplus$，xor）的定义：将两个数写成二进制，某位结果为 $1$ 当且仅当两个数在该位恰好有一个为 $1$。例如 $14 \oplus 7 = 9$。

输入格式

输入包含多个测试数据。

第一行一个整数 $t$ $(1 \leq t \leq 100)$，表示测试数据数量。

接下来依次描述每组测试数据：

• 第一行三个整数 $n, m, x$ $(1 \leq n, m \leq 500000,\ 0 \leq x < 2^{30})$
• 第二行 $n$ 个整数 $a_1, \dots, a_n$ $(0 \leq a_i < 2^{30})$
• 第三行 $m$ 个整数 $b_1, \dots, b_m$ $(0 \leq b_i < 2^{30})$

保证所有测试数据的 $n$ 之和以及 $m$ 之和均不超过 $500000$。

输出格式

对每组测试数据输出一行一个整数，表示最小的 $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

数据范围与提示

详细子任务附加限制及分值如下表所示：