Bad Wiring

A hallway contains a row of $n$ lights $L_1, L_2, \ldots, L_n$. Each light is either on or off. For every light $L_i$ there is one switch $S_i$.

Because of faulty wiring, flipping switch $S_i$ does not only toggle light $L_i$: it toggles every light whose position is within distance $D$ of $i$. That is, all of the lights $L_{i-D}, \ldots, L_{i+D}$ that actually exist have their state flipped. (To toggle means a light that is on turns off, and a light that is off turns on.)

For example, $S_1$ toggles $L_1, \ldots, L_{D+1}$ and $S_n$ toggles $L_{n-D}, \ldots, L_n$; if $D \ge n$, the out-of-range lights simply do not exist and are ignored.

Turn every light off using as few switch flips as possible. Determine the minimum number of switch flips needed to turn all lights off, or report that it is impossible.

The first line contains a single integer $T$, the number of test cases. Each test case consists of two lines:

• The first line contains two integers $n$ and $D$ ($1 \le n \le 100$, $0 \le D \le 15$): the number of lights and the range parameter described above.
• The second line contains $n$ integers. The $i$-th integer is the current state of light $L_i$, where $0$ means off and $1$ means on.

For each test case, output a single line containing one integer: the minimum number of switch flips needed to turn all lights off. If it is impossible to turn all lights off, output the string impossible instead.

When $n = 7$, $D = 3$ and the lights are 1 1 1 0 0 0 0, flipping switch $S_4$ and then $S_7$ turns all the lights off.