Kevin has an integer sequence $a$ of length $n$. At the same time, Kevin has $m$ types of magic, where the $i$-th type of magic can be represented by an integer $b_i$.

Kevin can perform at most $k$ (possibly zero) magic operations. In each operation, Kevin can do the following:

• Choose two indices $i$ ($1\leq i\leq n$) and $j$ ($1\leq j\leq m$), and then update $a_i$ to $a_i\ \&\ b_j$. Here, $\&$ denotes the bitwise AND operation.

Find the minimum possible sum of all numbers in the sequence $a$ after performing at most $k$ operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n, m, k$ ($1\leq n \leq 10^5$, $1\leq m \leq 10$, $0\leq k\leq nm$) — the length of $a$, the number of types of magic, and the maximum number of operations.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0\leq a_i \lt 2^{30}$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($0\leq b_i \lt 2^{30}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output one integer — the minimum possible sum of all numbers in the sequence $a$ after performing at most $k$ operations.

Note

In the first test case, one possible way could be:

• Update $a_1$ to $a_1\ \&\ b_1$. The sequence will become $[5]$.
• Update $a_1$ to $a_1\ \&\ b_3$. The sequence will become $[1]$.

In the second test case, one possible way could be:

• Update $a_1$ to $a_1\ \&\ b_3$. The sequence will become $[1, 6]$.
• Update $a_2$ to $a_2\ \&\ b_3$. The sequence will become $[1, 2]$.