Kevin 有一个长度为 $n$ 的整数序列 $a$。同时，Kevin 拥有 $m$ 种魔法，其中第 $i$ 种魔法可以用一个整数 $b_i$ 表示。

Kevin 最多可以进行 $k$ 次（可以为零次）魔法操作。在每次操作中，Kevin 可以执行以下操作：

• 选择两个下标 $i$ ($1 \le i \le n$) 和 $j$ ($1 \le j \le m$)，然后将 $a_i$ 更新为 $a_i \ \& \ b_j$。这里 $\&$ 表示按位与（bitwise AND）操作。

求在进行最多 $k$ 次操作后，序列 $a$ 中所有数字之和的最小可能值。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

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

每个测试用例的第一行包含三个整数 $n, m, k$ ($1 \le n \le 10^5$, $1 \le m \le 10$, $0 \le k \le nm$) —— 分别表示序列 $a$ 的长度、魔法的种类数以及最大操作次数。

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

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($0 \le b_i < 2^{30}$)。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 表示在进行最多 $k$ 次操作后，序列 $a$ 中所有数字之和的最小可能值。

样例

输入样例 1

5
1 3 2
7
5 6 3
2 3 2
5 6
5 6 3
10 2 5
3 1 4 1 5 9 2 6 5 3
7 8
5 1 0
1073741823 1073741823 1073741823 1073741823 1073741823
1073741823
1 1 0
0
0

输出样例 1

1
3
11
5368709115
0

说明

在第一个测试用例中，一种可行的方法如下：

• 将 $a_1$ 更新为 $a_1 \ \& \ b_1$。序列将变为 $[5]$。
• 将 $a_1$ 更新为 $a_1 \ \& \ b_3$。序列将变为 $[1]$。

在第二个测试用例中，一种可行的方法如下：

• 将 $a_1$ 更新为 $a_1 \ \& \ b_3$。序列将变为 $[1, 6]$。
• 将 $a_2$ 更新为 $a_2 \ \& \ b_3$。序列将变为 $[1, 2]$。