D. hsq 的神秘序列
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

hsq 最近在研究二进制位运算 。 他发现了两个神秘的序列 $$$A$$$ 和 $$$B$$$ , 分别包含 $$$N$$$ 和 $$$M$$$ 个 互不相同 的非负整数 。 序列中的所有元素均严格小于 $$$2^K$$$ 。

你需要分别从序列 $$$A$$$ 和序列 $$$B$$$ 中选择一些元素 , 分别构成新的序列 $$$A'$$$ 和 $$$B'$$$ , 使得满足以下所有条件 :

  • $$$A'$$$ 是 $$$A$$$ 的子序列 , $$$B'$$$ 是 $$$B$$$ 的子序列 。
  • $$$A'$$$ 和 $$$B'$$$ 的长度相等 , 设其长度为 $$$L$$$ 。
  • 对于任意 $$$1 \le j \le L$$$ , 选择的元素对 ( $$$A'_j$$$ , $$$B'_j$$$ ) 必须满足 : $$$A'_j \oplus B'_j = 2^K - 1$$$ 。

$$$\oplus$$$ 表示按位异或 （bitwise XOR） 运算 。

请你计算并输出 $$$L$$$ 的最大可能值 。

Input

输入的第一行包含一个正整数 $$$T$$$ , 表示测试数据的组数 。

对于每组测试数据 : 第一行包含三个正整数 $$$N$$$ , $$$M$$$ , $$$K$$$ ( $$$1 \le N , M \le 10^5$$$ , $$$1 \le K \lt 31$$$ ) , 分别表示序列 $$$A$$$ 的长度 、 序列 $$$B$$$ 的长度以及二进制位数 。

第二行包含 $$$N$$$ 个非负整数 $$$A_1 , A_2 , \dots , A_N$$$ ( $$$0 \le A_i \lt 2^K$$$ ) , 表示序列 $$$A$$$ 的元素 。 保证序列 $$$A$$$ 中的元素互不相同 。

第三行包含 $$$M$$$ 个非负整数 $$$B_1 , B_2 , \dots , B_M$$$ ( $$$0 \le B_i \lt 2^K$$$ ) , 表示序列 $$$B$$$ 的元素 。 保证序列 $$$B$$$ 中的元素互不相同 。

数据保证

所有测试数据的 $$$N$$$ 之和不超过 $$$10^5$$$ 。

所有测试数据的 $$$M$$$ 之和不超过 $$$10^5$$$ 。

Output

对于每组测试数据 , 输出一行一个整数 , 表示 $$$L$$$ 的最大可能值 。

Example
Input
2
3 3 3
1 4 2
5 6 3
4 4 4
1 2 4 8
14 13 11 7
Output
2
4
Note

对于第一组测试数据 , 我们可以选择的子序列为 $$$A' = [1 , 4]$$$ 和 $$$B' = [6 , 3]$$$ , 此时最大长度为 $$$2$$$ 。

对于第二组测试数据 , 我们可以选择的子序列为 $$$A' = [1 , 2 , 4 , 8]$$$ 和 $$$B' = [14 , 13 , 11 , 7]$$$ , 此时最大长度为 $$$4$$$ 。