题目描述

给定两个长度为 $n$ 的整数数组 $q=(q_1,q_2,\dots,q_n)$ 和 $r=(r_1,r_2,\dots,r_n)$，以及一个整数上界 $k$。

你可以进行若干次以下操作（次数不限）：

• 选取两个整数 $x,y$ 满足 $1 \le y < x \le k$；
• 存在一个下标 $i$ 使得 $q_i=\left\lfloor \dfrac{x}{y} \right\rfloor$（即向下取整的商）；
• 存在一个下标 $j$ 使得 $r_j = x \bmod y$（即余数）；

若满足以上条件，则从数组 $q$ 中删除一个值为 $\left\lfloor \dfrac{x}{y} \right\rfloor$ 的元素（若有多个，只删除其中一个），并从数组 $r$ 中删除一个值为 $x\bmod y$ 的元素（同样只删除一个）。每次删除视为一次操作。

问：在给定的 $q$、$r$ 和 $k$ 的条件下，最多可以执行多少次这样的操作？

输入格式

第一行包含一个整数 $t$，表示测试用例的数量（$1\le t \le 10^4$）。

每个测试用例包含三行：

• 第一行包含两个整数 $n$ 和 $k$，满足 $1\le n\le 2\cdot 10^5$，$2\le k\le 10^{18}$；
• 第二行包含 $n$ 个整数 $q_1,q_2,\dots,q_n$，满足 $1\le q_i\le 10^9$；
• 第三行包含 $n$ 个整数 $r_1,r_2,\dots,r_n$，满足 $1\le r_i\le 10^9$。

数据保证所有测试用例中 $\sum n \le 2\cdot 10^5$。

输出格式

对每个测试用例，输出一行，包含一个整数——在该测试用例下能够执行的最多操作次数。

样例输入

3
1 100
1
27
3 10
5 6 5
7 1 7
5 42
5 4 2 2 1
9 8 9 8 100

样例输出

1
0
3

说明

样例解释

• 第一个测试用例：可以取 $x=69,y=42$，则 $\lfloor \frac{69}{42}\rfloor=1=q_1$ 且 $69\bmod42=27=r_1$，可做一次操作。

• 第二个测试用例：不存在满足条件的 $(x,y)$，因此不能做任何操作。

• 第三个测试用例：可以依次做三次操作（示例之一）：

  • $x=42,y=17$：$\lfloor\frac{42}{17}\rfloor=2=q_3$，$42\bmod17=8=r_2$；
  • $x=41,y=16$：$\lfloor\frac{41}{16}\rfloor=2=q_4$，$41\bmod16=9=r_1$；
  • $x=20,y=12$：$\lfloor\frac{20}{12}\rfloor=1=q_5$，$20\bmod12=8=r_4$。

  执行后剩余 $q=[5,4]$，$r=[9,100]$，无法再继续。