Погана проводка
Ніндзя Рю проник у фортецю клану Тіней і опинився в довгому коридорі. Хоча ніндзя є відмінними бійцями, вони в основному покладаються на скритність для виконання своїх місій. Однак у коридорі ввімкнено багато світла, і таким чином, Рю незабаром помітить охоронець. Щоб залишитися непоміченим, Рю потрібно якомога швидше вимкнути всі світла.
У коридорі є послідовність з 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 означає увімкнено.
Вихідні дані
Для кожного тестового випадку у вхідних даних вихід повинен містити одне ціле число в одному рядку: мінімальну кількість разів, які Рю повинен натиснути вимикач, щоб вимкнути всі світла. Якщо неможливо вимкнути всі світла, виведіть рядок "неможливо" замість цього.
Приклад
У першому прикладі нижче, натискання вимикача S_4, а потім S_7 вимкне всі світла.