当前没有测试数据。

题目描述

给定一个包含 $n$ 个正整数的多重集合 $a$。

你可以执行任意次（可以为 0）如下操作：

• 从多重集合中选取一个大于 $1$ 的整数 $x$，再选取 $x$ 的一个质因子 $p$。从多重集合中删除一个 $x$，然后加入 $p$ 个 $\dfrac{x}{p}$。

同时给定整数 $k$（$1 \le k \le n$）。定义 $f(k)$：从原始多重集合开始，直到集合内所有数都不超过 $k$，所需要的最少操作次数。

求出 $f(k)$。

输入格式

多组测试用例。第一行一个整数 $t$（$1 \le t \le 10^4$），代表测试用例数量。

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

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le n$），代表多重集合内的元素。

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

输出格式

对每组测试用例输出一个整数 $f(k)$。

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

说明

第一个测试用例，唯一的元素本身就小于等于 $k$，不需要任何操作。

第二个测试用例，可以按下面步骤执行操作：

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

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

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

$[2,2,2,2,2,2,2,2,\textcolor{red}{3},2,1] \rightarrow [2,2,2,2,2,2,2,2,\textcolor{red}{1,1,1},2,1]$。

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

原题链接

原题链接