给定两个整数数组:$$$q_1、q_2、\dots、q_n$$$ 和 $$$r_1、r_2、\dots、r_n$$$,以及一个整数 $$$k$$$。
您可以执行以下操作任意次数(可能为零):
- 选择两个整数 $$$x$$$ 和 $$$y$$$ 使得
- $$$1 \le y \lt x \le k$$$;
- 存在一个索引 $$$i$$$ 使得 $$$q_i = \left\lfloor \frac{x}{y} \right\rfloor$$$ (向下舍入);
- 存在一个索引 $$$j$$$ 使得 $$$r_j = x \bmod y$$$。
- 从数组 $$$q$$$ 中删除 $$$q_i$$$ 并从数组 $$$r$$$ 中删除 $$$r_j$$$。如果数组 $$$q$$$ 中多次出现 $$$q_i$$$,则只删除其中的一个; $$$r_j$$$ 和数组 $$$r$$$ 相同。
计算可以对给定数组 $$$q$$$ 和 $$$r$$$ 执行的最大操作数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le 10^{18}$$$) - 数组 $$$q$$$ 和 $$$r$$$ 的大小以及 $$$x$$$ 的上限和$$$y$$$。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$q_1, q_2, \dots, q_n$$$ ($$$1 \le q_i \le 10^9$$$) — 数组 $$$q$$$。
第三行包含 $$$n$$$ 整数 $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^9$$$) — 数组 $$$r$$$。
输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 您可以对给定数组执行的最大操作数。
示例
输入复制
31 1001273 105 6 57 1 75 425 4 2 2 19 8 9 8 100
输出复制
103
注意
在第一个测试用例中,可以执行一个操作:您可以选择 $$$x = 69$$$ 和 $$$y = 42$$$。然后 $$$\left\lfloor \frac{69}{42} \right\rfloor = 1 = q_1$$$ 和 $$$69 \bmod 42 = 27 = r_1$$$。
在第二个测试用例中,无法执行任何操作,因为找不到合适的 $$$x$$$ 和 $$$y$$$。
在第三个测试用例中,可以执行三个操作:
- $$$x = 42$$$, $$$y = 17$$$: $$$\left\lfloor \frac{42}{17} \right\rfloor = 2 = q_3$$$ 和 $$$42 \bmod 17 = 8 = r_2$$$;
- $$$x = 41$$$,$$$y = 16$$$:$$$\left\lfloor \frac{41}{16} \right\rfloor = 2 = q_4$$$ 和 $$$41 \bmod 16 = 9 = r_1$$$;
- $$$x = 20$$$,$$$y = 12$$$:$$$\left\lfloor \frac{20}{12} \right\rfloor = 1 = q_5$$$ 和 $$$20 \bmod 12 = 8 = r_4$$$;