Плохая проводка
Ниндзя Рю проник в крепость клана Тени и оказался в длинном коридоре. Хотя ниндзя — отличные бойцы, они в первую очередь полагаются на скрытность для выполнения своих миссий. Однако в коридоре включено много света, и вскоре Рю может заметить охранник. Чтобы остаться незамеченным, Рю нужно как можно быстрее выключить все огни.
В коридоре расположена последовательность из n ламп L_1...L_n. Некоторые из этих ламп включены. Разрушение ламп с помощью сюрикенов было бы слишком шумным, поэтому ему нужно выключить их по старинке, используя выключатели. К счастью, рядом находится распределительная коробка с выключателем S_i для каждой лампы L_i. Однако, попробовав один из выключателей, он замечает кое-что интересное. Когда он переключает выключатель S_i, это не только включает/выключает лампу L_i, но и некоторые соседние лампы. Рю замечает, что существует параметр D, такой что переключение выключателя S_i включает/выключает все лампы L_{i-D}...L_{i+D}, если они существуют (это означает, что S_1 включает/выключает все лампы L_1...L_{D+1} и S_n включает/выключает все лампы L_{n-D}...L_n. Конечно, если D ≥ n, то L_{D+1} и L_{n-D} также не будут существовать). Включение или выключение ламп может привлечь внимание охранников, поэтому Рю хотел бы выключить все лампы с минимальным количеством переключений. Можете ли вы ему помочь?
Входные данные
Первая строка входных данных содержит одно число: количество тестов, которые следует выполнить. Каждый тест имеет следующий формат:
Одна строка с двумя целыми числами n (1 ≤ n ≤ 100) и D (0 ≤ D ≤ 15): количество ламп и упомянутый выше параметр.
Одна строка с n целыми числами. i-е число описывает текущее состояние лампы L_i, где 0 означает выключено, а 1 означает включено.
Выходные данные
Для каждого теста во входных данных вывод должен содержать одно целое число в отдельной строке: минимальное количество раз, которое Рю нужно переключить выключатель, чтобы выключить все лампы. Если невозможно выключить все лампы, выведите строку "impossible".
Пример
В первом примере ниже, переключение выключателя S_4, а затем S_7 выключит все лампы.