CF2266E.Prime Destruction

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

给你一个由 $n$ 个正整数组成的多重集 $a$。

你可以执行以下操作任意次（包括零次）：

• 从多重集中选择一个整数 $x \gt 1$ 及其一个质因数 $p$。从多重集中移除一个 $x$，并添加 $p$ 个 $\frac{x}{p}$。

你还给定一个整数 $k$（$1 \le k \le n$）。令 $f(k)$ 表示：从原始多重集出发，经过最少多少次操作后，多重集中所有整数均不超过 $k$。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$），分别表示多重集的初始大小和给定的整数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示多重集的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出一个整数 $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.

在第一个测试用例中，唯一的元素本身已不超过 $k$，因此无需任何操作。

在第二个测试用例中，我们可以执行以下操作：

$[\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]$。

因此，$4$ 次操作已足够。可以证明，不存在操作次数严格更少的方案。