F. Стабилизируй массив (И-версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив из нулей и единиц $$$a[0 \ldots n - 1] = [a_0, a_1, \ldots, a_{n - 1}]$$$. Обратите внимание, что в этой задаче, в отличие от остальных, индексы массива нумеруются с нуля, а не с единицы.

За один шаг массив $$$a$$$ заменяется на другой массив длины $$$n$$$ по следующим правилам:

  1. Сначала строится новый массив $$$a^{\rightarrow d}$$$ — циклический сдвиг массива $$$a$$$ вправо на $$$d$$$ ячеек. Элементы этого массива определяются как $$$a^{\rightarrow d}_i = a_{(i + n - d) \bmod n}$$$, где $$$(i + n - d) \bmod n$$$ — остаток от деления $$$i + n - d$$$ на $$$n$$$.

    Таким образом весь массив $$$a^{\rightarrow d}$$$ можно записать как $$$$$$a^{\rightarrow d} = [a_{n - d}, a_{n - d + 1}, \ldots, a_{n - 1}, a_0, a_1, \ldots, a_{n - d - 1}]$$$$$$

  2. Затем каждый элемент массива $$$a_i$$$ заменяется на $$$a_i \,\&\, a^{\rightarrow d}_i$$$, где $$$\&$$$ — операция логического «И».

Например, если $$$a = [0, 0, 1, 1]$$$ и $$$d = 1$$$, то $$$a^{\rightarrow d} = [1, 0, 0, 1]$$$, и значение $$$a$$$ после первого шага будет равно $$$[0 \,\&\, 1, 0 \,\&\, 0, 1 \,\&\, 0, 1 \,\&\, 1]$$$, то есть $$$[0, 0, 0, 1]$$$.

Процесс завершается, когда массив перестает меняться. Для заданного массива $$$a$$$ определите, будет ли он состоять из одних нулей по окончании процесса. Если да, то также найдите количество шагов, которое процесс совершит до своего завершения.

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

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

В следующих $$$2t$$$ строках даны описания наборов входных данных.

В описании каждого набора входных данных первая строка содержит два целых числа: $$$n$$$ ($$$1 \le n \le 10^6$$$) — размер массива, и $$$d$$$ ($$$1 \le d \le n$$$) — размер сдвига массива на каждом шаге. Во второй строке описания через пробел записаны $$$n$$$ чисел $$$a_i$$$ ($$$0 \le a_i \le 1$$$) — элементы исходного массива.

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

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

Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите одно целое число — количество шагов, после которого массив впервые станет состоять из всех нулей. Если же после завершения процесса в массиве все еще будут присутствовать единицы, выведите -1.

Пример
Входные данные
5
2 1
0 1
3 2
0 1 0
5 2
1 1 0 1 0
4 2
0 1 0 1
1 1
0
Выходные данные
1
1
3
-1
0
Примечание

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

  1. В начале $$$a = [1, 1, 0, 1, 0]$$$, и $$$a^{\rightarrow 2} = [1, 0, 1, 1, 0]$$$. Их поэлементное «И» равно $$$$$$[1 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 1, 0 \,\&\, 0] = [1, 0, 0, 1, 0]$$$$$$
  2. Теперь $$$a = [1, 0, 0, 1, 0]$$$, тогда $$$a^{\rightarrow 2} = [1, 0, 1, 0, 0]$$$. Их поэлементное «И» равно $$$$$$[1 \,\&\, 1, 0 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 0] = [1, 0, 0, 0, 0]$$$$$$
  3. И, наконец, при $$$a = [1, 0, 0, 0, 0]$$$ получаем $$$a^{\rightarrow 2} = [0, 0, 1, 0, 0]$$$. Их поэлементное «И» равно $$$$$$[1 \,\&\, 0, 0 \,\&\, 0, 0 \,\&\, 1, 0 \,\&\, 0, 0 \,\&\, 0] = [0, 0, 0, 0, 0]$$$$$$
Таким образом, ответ — $$$3$$$ итерации.

В четвертом наборе входных данных массив не будет изменяться при сдвиге на $$$2$$$ вправо, потому что каждый элемент будет вычисляться как $$$0 \,\&\, 0$$$ или $$$1 \,\&\, 1$$$. Таким образом, единицы останутся на своих местах, и ответ — -1, массив никогда не будет состоять только из нулей.