E. Разрушение простых
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано мультимножество $$$a$$$, состоящее из $$$n$$$ положительных целых чисел.

Вы можете выполнять следующую операцию любое количество раз (возможно, ноль):

  • Выберите целое число $$$x \gt 1$$$ из мультимножества и простой делитель $$$p$$$ числа $$$x$$$. Удалите одно вхождение $$$x$$$ из мультимножества и добавьте $$$p$$$ копий числа $$$\frac{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$$$) — начальный размер мультимножества и заданное целое число соответственно.

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, 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$$$, поэтому операций не требуется.

Во втором наборе входных данных можно выполнить следующие операции:

$$$[\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$$$ операций. Можно показать, что последовательности с меньшим числом операций не существует.