Bad Wiring

복도에 전등 $n$개가 $L_1, L_2, \ldots, L_n$ 순서로 한 줄로 놓여 있다. 각 전등은 켜져 있거나 꺼져 있다. 전등 $L_i$마다 스위치 $S_i$가 하나씩 있다.

배선이 잘못되어 있어서, 스위치 $S_i$를 누르면 전등 $L_i$ 하나만 바뀌는 것이 아니라 위치 차이가 $D$ 이하인 모든 전등이 함께 토글된다. 즉 실제로 존재하는 $L_{i-D}, \ldots, L_{i+D}$ 가 모두 상태가 반전된다. (토글이란 켜진 전등은 꺼지고, 꺼진 전등은 켜지는 것을 뜻한다.)

예를 들어 $S_1$은 $L_1, \ldots, L_{D+1}$을 토글하고 $S_n$은 $L_{n-D}, \ldots, L_n$을 토글한다. 만약 $D \ge n$이면 범위를 벗어나는 전등은 존재하지 않으므로 무시한다.

스위치를 최소 몇 번 눌러 모든 전등을 끌 수 있는지 구하여라. 모든 전등을 끄는 것이 불가능하면 그 사실을 알려라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음 두 줄로 이루어진다.

• 첫 줄에 두 정수 $n$과 $D$ ($1 \le n \le 100$, $0 \le D \le 15$)가 주어진다. $n$은 전등의 수, $D$는 위에서 설명한 범위 값이다.
• 둘째 줄에 $n$개의 정수가 주어진다. $i$번째 정수는 전등 $L_i$의 현재 상태이며, $0$은 꺼짐, $1$은 켜짐을 뜻한다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 이 값은 모든 전등을 끄기 위해 스위치를 누르는 최소 횟수이다. 모든 전등을 끄는 것이 불가능하면 대신 impossible 을 출력한다.

$n = 7$, $D = 3$ 이고 전등 상태가 1 1 1 0 0 0 0 인 경우, 스위치 $S_4$를 누른 뒤 $S_7$을 누르면 모든 전등이 꺼진다.