Погана проводка#3126
Ніндзя Рю проник до фортеці Клану Тіней і опинився в довгому коридорі. Хоча ніндзя — чудові бійці, вони переважно покладаються на скритність для виконання своїх місій. Однак у коридорі увімкнено багато світла, і це дозволяє охоронцям легко помітити Рю. Щоб залишитися непоміченим, Рю має якнайшвидше вимкнути всі ліхтарі.
У коридорі знаходиться послідовність з ліхтарів L_1 \ldots L_n. Деякі з них увімкнені. Руйнувати ліхтарі сюріканами було б занадто гучно, тож він мусить вимикати їх за допомогою вимикачів. На щастя, поблизу є щиток із вимикачем S_i для кожного ліхтаря L_i. Проте, спробувавши один із вимикачів, він помічає цікаву річ: перемикання вимикача S_i змінює стан не лише ліхтаря L_i, а й деяких сусідніх. Рю помічає, що існує параметр , такий, що перемикання вимикача S_i змінює стан усіх ліхтарів L_{i-D} \ldots L_{i+D}, якщо вони існують. (Тобто S_1 змінює стан L_1 \ldots L_{D+1}, а S_n — L_{n-D} \ldots L_n. Звісно, якщо D \geq n, то L_{D+1} і L_{n-D} не існуватимуть.) Вмикання чи вимикання ліхтарів може привернути увагу охоронців, тому Рю хоче вимкнути всі ліхтарі мінімальною кількістю натискань на вимикачі. Чи зможете ви допомогти йому?
Перший рядок вхідних даних містить одне ціле число — кількість тестових випадків. Кожен тестовий випадок має такий формат:
Один рядок з двома цілими числами (1 \leq n \leq 100) і (0 \leq D \leq 15): кількість ліхтарів і відповідний параметр.
Один рядок зі цілих чисел. -те число задає поточний стан ліхтаря L_i, де означає вимкнено, а — увімкнено.
Для кожного тестового випадку виведіть одне ціле число: мінімальну кількість натискань на вимикачі, потрібну Рю, щоб вимкнути всі ліхтарі. Якщо це неможливо, виведіть рядок impossible.
Приклад
У першому прикладі нижче, вимкнути всі ліхтарі можна, натиснувши спочатку вимикач S_4, а потім S_7.
Приклад 1