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:

Select an index $$$i$$$ ($$$1 \leq i \leq n$$$) and set $$$a_i := a_i + 1$$$.
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.

AND x OR

Examples