C. Quotient and Remainder
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given two integer arrays: $$$q_1, q_2, \dots, q_n$$$ and $$$r_1, r_2, \dots, r_n$$$, as well as an integer $$$k$$$.

You can perform the following operation any number of times (possibly zero):

  1. Choose two integers $$$x$$$ and $$$y$$$ such that
    • $$$1 \le y \lt x \le k$$$;
    • there exists an index $$$i$$$ such that $$$q_i = \left\lfloor \frac{x}{y} \right\rfloor$$$ (rounded down);
    • there exists an index $$$j$$$ such that $$$r_j = x \bmod y$$$.
  2. Remove $$$q_i$$$ from the array $$$q$$$ and $$$r_j$$$ from the array $$$r$$$. If there are multiple occurrences of $$$q_i$$$ in the array $$$q$$$, only one occurrence is removed; same for $$$r_j$$$ and the array $$$r$$$.

Calculate the maximum number of operations that you can perform on the given arrays $$$q$$$ and $$$r$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le 10^{18}$$$) — the size of the arrays $$$q$$$ and $$$r$$$ and the upper limit for $$$x$$$ and $$$y$$$.

The second line of each test case contains $$$n$$$ integers $$$q_1, q_2, \dots, q_n$$$ ($$$1 \le q_i \le 10^9$$$) — the array $$$q$$$.

The third line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^9$$$) — the array $$$r$$$.

Additional constraints on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print one integer — the maximum number of operations that you can perform on the given arrays.

Example
Input
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
Output
1
0
3
Note

In the first test case, one operation can be performed: you can choose $$$x = 69$$$ and $$$y = 42$$$. Then $$$\left\lfloor \frac{69}{42} \right\rfloor = 1 = q_1$$$ and $$$69 \bmod 42 = 27 = r_1$$$.

In the second test case, it is impossible to perform any operations, as suitable $$$x$$$ and $$$y$$$ cannot be found.

In the third test case, three operations can be performed:

  1. $$$x = 42$$$, $$$y = 17$$$: $$$\left\lfloor \frac{42}{17} \right\rfloor = 2 = q_3$$$ and $$$42 \bmod 17 = 8 = r_2$$$;
  2. $$$x = 41$$$, $$$y = 16$$$: $$$\left\lfloor \frac{41}{16} \right\rfloor = 2 = q_4$$$ and $$$41 \bmod 16 = 9 = r_1$$$;
  3. $$$x = 20$$$, $$$y = 12$$$: $$$\left\lfloor \frac{20}{12} \right\rfloor = 1 = q_5$$$ and $$$20 \bmod 12 = 8 = r_4$$$;
After these operations, you'll get arrays $$$q = [5, 4]$$$ and $$$r = [9, 100]$$$, and there are no more operations you can perform.