CF2266E Prime Destruction

You are given a [multiset](https://en.wikipedia.org/wiki/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) $ .

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 $ .

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

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.