E. Prime Destruction
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a multiset $$$a$$$ consisting of $$$n$$$ positive integers.

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

  • Choose an integer $$$x \gt 1$$$ from the multiset and a prime divisor $$$p$$$ of $$$x$$$. Remove one occurrence of $$$x$$$ from the multiset and add $$$p$$$ copies of $$$\frac{x}{p}$$$.

You are also given an integer $$$k$$$ ($$$1 \le k \le n$$$). Let $$$f(k)$$$ be the minimum number of operations required, starting from the original multiset, until every integer in the multiset is at most $$$k$$$.

Find $$$f(k)$$$.

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 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the initial size of the multiset and the given integer, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the multiset.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer $$$f(k)$$$.

Example
Input
6
1 1
1
6 2
6 6 4 3 2 1
8 1
8 6 4 3 2 1 8 6
12 3
12 10 9 8 7 6 5 4 3 2 1 12
10 9
10 9 8 7 6 5 4 3 2 1
5 5
5 4 3 2 1
Output
0
4
25
15
1
0
Note

In the first test case, the only element is already at most $$$k$$$, so no operations are needed.

In the second test case, we can perform the following operations:

$$$[\color{red}{6},6,4,3,2,1] \rightarrow [\color{red}{2,2,2},6,4,3,2,1]$$$,

$$$[2,2,2,\color{red}{6},4,3,2,1] \rightarrow [2,2,2,\color{red}{2,2,2},4,3,2,1]$$$,

$$$[2,2,2,2,2,2,\color{red}{4},3,2,1] \rightarrow [2,2,2,2,2,2,\color{red}{2,2},3,2,1]$$$,

$$$[2,2,2,2,2,2,2,2,\color{red}{3},2,1] \rightarrow [2,2,2,2,2,2,2,2,\color{red}{1,1,1},2,1]$$$.

Thus, $$$4$$$ operations are sufficient. It can be shown that no sequence with strictly fewer operations exists.