Suppose you have two arrays $c$ and $d$, each of length $k$. The pair $(c, d)$ is called good if $c$ can be changed to $d$ by performing the following operation any number of times.

• Select two distinct indices $i$ and $j$ ($1 \leq i, j \leq k$, $i \neq j$) and a nonnegative integer $x$ ($0 \leq x \lt 2^{30}$). Then, apply the following transformations:
• $c_i := c_i \mathbin{\&} x$, where $\&$ denotes the bitwise AND operation.
  • $c_j := c_j \mathbin{|} x$, where $|$ denotes the bitwise OR operation.

You are given two arrays $a$ and $b$, both of length $n$, containing nonnegative integers not exceeding $m$.

You can perform two types of moves on these arrays any number of times:

1. Select an index $i$ ($1 \leq i \leq n$) and set $a_i := a_i + 1$.
2. Select an index $i$ ($1 \leq i \leq n$) and set $b_i := b_i + 1$.

Note that the elements of $a$ and $b$ may exceed $m$ at some point while performing the moves.

Find the minimum number of moves required to make the pair $(a, b)$ good.

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 two integers $n$ and $m$ ($1 \leq n, m \leq 2 \cdot 10^6$) — the length of arrays $a$ and $b$, and the maximum possible value in these arrays, respectively.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq m$) — denoting the array $a$.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \leq b_i \leq m$) — denoting the array $b$.

Additionally, it is guaranteed that the sum of all values of $n$ and the sum of all values of $m$ across all test cases do not exceed $2 \cdot 10^6$.

Output

For each test case, output a single integer — the minimum number of moves required to make the pair $(a, b)$ good.

Note

In the first case, we already have $a = b$.

In the second case, we can perform move $2$ on index $i = 2$ twice. The array $b$ becomes $[8, 8, 32]$. We can see that $(a, b)$ is now good.

In the third case, we can perform move $2$ on index $i = 1$, then perform move $1$ on index $i = 2$. It can be proven that you cannot make the pair $(a, b)$ good in fewer than $2$ moves.