#CF2266E. Prime Destruction
Prime Destruction
Problem Description
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 Format
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 Format
For each test case, print a single integer $f(k)$.
Examples
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
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.
Source
Imported from Codeforces — Codeforces Round 1122 (Div. 3).