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

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

要求找到最小的整数 $k$，使得可以将数组 $A$ 的元素染成 $k$ 种颜色，并且满足：如果 $S(x)$ 与 $S(y)$ 有交集，那么 $x$ 和 $y$ 必须被染成不同的颜色。

也就是说，需要找到颜色 $c_1,c_2,\dots,c_n$，满足 $1\le c_i\le k$，并且如果 $S(x)\cap S(y)\ne\varnothing$，则 $c_x\ne 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\le x< 2^{30}$)。

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

第三行包含 $m$ 个整数 $b_1,b_2,\dots,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