E. Three Days Grace
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ibti раздумывал о хорошем названии для этой задачи, которое подойдёт к теме раунда (число три). Он сразу подумал о третьей производной, но это было довольно глупо, поэтому он решил включить лучшую группу в мире — Three Days Grace.

Вам дано мультимножество $$$A$$$ изначального размера $$$n$$$, элементы которого — целые числа от $$$1$$$ до $$$m$$$. За одну операцию можно сделать следующее:

  • выбрать значение $$$x$$$ из мультимножества $$$A$$$, затем
  • выбрать два целых числа $$$p$$$ и $$$q$$$ такие, что $$$p, q > 1$$$ и $$$p \cdot q = x$$$. Добавить $$$p$$$ и $$$q$$$ в $$$A$$$, удалить $$$x$$$ из $$$A$$$.

Заметьте, что размер мультимножества $$$A$$$ увеличивается на $$$1$$$ после каждой операции.

Назовём балансом мультимножества $$$A$$$ значение $$$\max(a_i) - \min(a_i)$$$. Найдите минимально возможный баланс после применения нескольких (возможно, нуля) операций.

Входные данные

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит целые числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 5 \cdot 10^6$$$) — изначальный размер мультимножества и максимально возможное значение числа в мультимножестве.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — элементы в изначальном мультимножестве.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^6$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — минимально возможный баланс.

Пример
Входные данные
4
5 10
2 4 2 4 2
3 50
12 2 3
2 40
6 35
2 5
1 5
Выходные данные
0
1
2
4
Примечание

В первом наборе входных данных мы можем применить операцию к каждому из чисел $$$4$$$ с $$$(p,q) = (2,2)$$$ и сделать мультимножество $$$\{2,2,2,2,2,2,2\}$$$ с балансом $$$\max(\{2,2,2,2,2,2,2\}) - \min(\{2,2,2,2,2,2,2\}) = 0$$$. Очевидно, мы не можем сделать баланс меньше $$$0$$$.

Во втором входных данных мы можем применить операция к $$$12$$$ с $$$(p,q) = (3,4)$$$. После этого мультимножество станет равным $$$\{3,4,2,3\}$$$. Мы можем применить ещё одну операцию к числу $$$4$$$ с $$$(p,q) = (2,2)$$$, сделав мультимножество $$$\{3,2,2,2,3\}$$$ с балансом $$$1$$$.

В третьем входных данных мы можем применить операцию к $$$35$$$ с $$$(p,q) = (5,7)$$$. Итоговое мультимножество будет $$$\{6,5,7\}$$$ с балансом $$$7-5 = 2$$$.

В четвёртом наборе входных данных мы не может применить никакую операцию, поэтому ответ равен $$$5 - 1 = 4$$$.