C. Максимальный НОД на доске
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$k$$$ и $$$n$$$ целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$, записанных на доске, где $$$1\le a_i\le \boldsymbol{n}$$$. Вы можете выполнять следующие операции:

  • Стереть: Выберите целое число с доски и сотрите его. Эту операцию можно выполнить не более $$$k$$$ раз.
  • Разделить: Выберите целое число $$$x\ge 3$$$ с доски. Разделите его на три целых положительных числа $$$x_1$$$, $$$x_2$$$ и $$$x_3$$$ так, чтобы выполнялось $$$x_1 + x_2 + x_3 = x$$$ и $$$1\le x_1\le x_2\le x_3$$$. Затем сотрите $$$x$$$ с доски и запишите два новых числа $$$x_1$$$ и $$$x_3$$$ на доске. Обратите внимание, что $$$x_2$$$ отбрасывается и не записывается на доске. Эту операцию можно выполнять любое количество раз.

Красота коллекции целых чисел $$$b$$$ определяется как наибольший общий делитель всех элементов в $$$b$$$. Формально, это наибольшее целое число $$$d$$$, такое что $$$d$$$ делит $$$x$$$ для каждого $$$x$$$, который является элементом $$$b$$$.

Ваша задача — определить максимальную возможную красоту чисел на доске после выполнения не более $$$k$$$ операций Стереть и любого количества операций Разделить.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1\le n \le 2 \cdot 10^5$$$, $$$0 \le k \le n - 1$$$) — количество чисел на доске и максимальное количество разрешенных операций Стереть.

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

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

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

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

Пример
Входные данные
6
9 1
4 9 6 8 2 6 7 8 2
10 1
4 9 6 8 2 6 7 8 2 7
7 5
1 1 2 3 4 5 5
7 4
1 1 2 3 4 5 5
14 3
14 12 7 12 9 9 12 4 3 1 3 6 9 13
1 0
1
Выходные данные
2
1
5
1
3
1
Примечание

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

  • Стереть $$$7$$$. Теперь на доске находятся числа $$$[4,9,6,8,2,6,8,2]$$$.
  • Разделить $$$9$$$ на три числа $$$2$$$, $$$3$$$ и $$$4$$$. $$$9$$$ стирается с доски, и записываются два новых числа $$$2$$$ и $$$4$$$. Теперь на доске находятся числа $$$[4,\underline{2,4},6,8,2,6,8,2]$$$.
  • Разделить $$$8$$$ на три числа $$$2$$$, $$$2$$$ и $$$4$$$. $$$8$$$ стирается с доски, и записываются два новых числа $$$2$$$ и $$$4$$$. Теперь на доске находятся числа $$$[4,2,4,6,\underline{2,4},2,6,8,2]$$$ (не имеет значения, на какой $$$8$$$ выполняется Разделить, так как порядок в массиве не имеет значения).

Красота чисел на доске после операций равна $$$2$$$, так как это наибольшее число, которое делит все числа на доске ($$$2$$$, $$$4$$$, $$$6$$$ и $$$8$$$). Обратите внимание, что последняя операция не является необходимой — красота чисел на доске после второй операции уже равна $$$2$$$.

Во втором наборе входных данных обратите внимание, что операция Стереть может удалить только одно вхождение числа, даже если существуют дубликаты. Здесь мы можем стереть только одну копию $$$7$$$, поэтому на доске останется одна $$$7$$$. Следовательно, мы не можем выполнить ту же последовательность операций, что и в первом наборе входных данных.

В третьем наборе входных данных мы можем стереть числа $$$1$$$, $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$, оставив только $$$[5, 5]$$$ на доске. Поскольку оба числа равны $$$5$$$, их наибольший общий делитель равен $$$5$$$, и максимальная красота равна $$$5$$$.