Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

B. Суммы массивов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неубывающий массив, состоящий из неотрицательных целых чисел $$$a_1, a_2, \ldots, a_n$$$. Также вам дано положительное целое число $$$k$$$.

Вы хотите найти $$$m$$$ неубывающих массивов, состоящих из неотрицательных целых чисел $$$b_1, b_2, \ldots, b_m$$$, таких что:

  • размер $$$b_i$$$ равен $$$n$$$ для всех $$$1 \leq i \leq m$$$;
  • для всех $$$1 \leq j \leq n$$$, $$$a_j = b_{1, j} + b_{2, j} + \ldots + b_{m, j}$$$. Другими словами, массив $$$a$$$ равен поэлементной сумме массивов $$$b_i$$$;
  • количество различных элементов массива $$$b_i$$$ не превосходит $$$k$$$ для всех $$$1 \leq i \leq m$$$.

Найдите минимальное возможное значение $$$m$$$ или сообщите, что ни одного возможного значения $$$m$$$ не существует.

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

В первой строке находится единственное целое число $$$t$$$ ($$$1 \leq t \leq 100$$$): количество наборов входных данных.

В первой строке описания каждого набора входных данных находятся два целых числа $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 100$$$, $$$1 \leq k \leq n$$$).

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 100$$$, $$$a_n > 0$$$).

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

Для каждого набора входных данных выведите единственное целое число: минимальное возможное значение $$$m$$$. Если таких $$$m$$$ не существует, выведите $$$-1$$$.

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

В первом наборе входных данных не существует ни одного возможного значения $$$m$$$, потому что все элементы всех массивов должны будут быть равными $$$0$$$. Но в этом случае невозможно получить $$$a_4 = 1$$$ как сумму нескольких нулей.

Во втором наборе входных данных мы можем взять $$$b_1 = [3, 3, 3]$$$. $$$1$$$ — это минимальное возможное значение $$$m$$$.

В третьем наборе входных данных мы можем взять $$$b_1 = [0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]$$$ и $$$b_2 = [0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2]$$$. Легко заметить, что $$$a_i = b_{1, i} + b_{2, i}$$$ для всех $$$i$$$ и количество различных элементов в каждом из массивов $$$b_1$$$ и $$$b_2$$$ равно $$$3$$$ (что не превосходит $$$3$$$). Можно доказать, что $$$2$$$ — это минимальное возможное значение $$$m$$$.