假设您有两个数组 $$$c$$$ 和 $$$d$$$,每个数组的长度为 $$$k$$$。 $$$(c, d)$$$ 被称为 好 如果通过执行以下操作任意多次可以将 $$$c$$$ 更改为 $$$d$$$。
- 选择两个不同的索引 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq k$$$, $$$i \neq j$$$) 和一个非负整数 $$$x$$$ ($$$0 \leq x \lt 2^{30}$$$)。然后,应用以下转换:
- $$$c_i := c_i \mathbin{\&} x$$$,其中 $$$\&$$$ 表示按位 AND 运算。
- $$$c_j := c_j \mathbin{|} x$$$,其中 $$$|$$$ 表示按位或运算。
给定两个数组 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$,包含不超过 $$$m$$$ 的非负整数。
您可以对这些数组执行两种类型的移动任意次数:
- 选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 并设置 $$$a_i := a_i + 1$$$。
- 选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 并设置 $$$b_i := b_i + 1$$$。
请注意,在执行移动时,$$$a$$$ 和 $$$b$$$ 的元素可能会在某个时刻超过 $$$m$$$。
求使 $$$(a, b)$$$ 配对良好所需的最少移动次数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^6$$$) - 数组 $$$a$$$ 和 $$$b$$$ 的长度,以及这些数组中的最大可能值。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq m$$$) — 表示数组 $$$a$$$。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i \leq m$$$) — 表示数组 $$$b$$$。
此外,保证所有测试用例中 $$$n$$$ 的所有值的总和以及 $$$m$$$ 的所有值的总和不超过 $$$2 \cdot 10^6$$$。
输出
对于每个测试用例,输出一个整数 - 使 $$$(a, b)$$$ 配对良好所需的最小移动次数。
示例
输入复制
54 30 1 2 30 1 2 33 328 9 328 6 325 645 7 16 32 644 8 16 32 644 119 1 4 38 11 6 25 107 9 5 4 23 10 6 5 9
输出复制
0 2 2 0 1
注意
在第一种情况下,我们已经有 $$$a = b$$$。
在第二种情况下,我们可以在索引 $$$i = 2$$$ 上执行两次移动 $$$2$$$ 。数组 $$$b$$$ 变为 $$$[8, 8, 32]$$$。我们可以看到 $$$(a, b)$$$ 现在很好。
在第三种情况下,我们可以对索引 $$$i = 1$$$ 执行 move $$$2$$$,然后对索引 $$$i = 2$$$ 执行 move $$$1$$$。可以证明,您无法在少于 $$$2$$$ 的移动中使 $$$(a, b)$$$ 成为良好的货币对。