Bad Wiring#3126
Ninja Ryu has infiltrated the Shadow Clan fortress and finds himself in a long hallway. Although ninjas are excellent fighters, they primarily rely on stealth to complete their missions. However, many lights are turned on in the hallway, and this makes it easy for a guard to spot Ryu. To remain unseen, Ryu must turn off all the lights as quickly as possible.
The hallway contains a sequence of lights L_1 \ldots L_n. Some of these lights are turned on. Destroying the lights with his shurikens would be too loud, so he must turn them off using the light switches. Luckily, there is a switch box nearby with a light switch S_i for every light L_i. However, after trying one of the switches, he notices something interesting: flipping switch S_i does not only turn on or off light L_i, but also some of the neighboring lights. Ryu observes that there is a parameter such that flipping switch S_i toggles all the lights L_{i-D} \ldots L_{i+D}, if they exist. (This means that S_1 toggles L_1 \ldots L_{D+1} and S_n toggles L_{n-D} \ldots L_n. Of course, if D \geq n, then L_{D+1} and L_{n-D} will not exist.) Turning lights on or off can attract the attention of the guards, so Ryu wants to turn off all the lights using the minimum number of switch flips. Can you help him?
The first line of the input contains one integer — the number of test cases. Each test case has the following format:
One line with two integers (1 \leq n \leq 100) and (0 \leq D \leq 15): the number of lights and the parameter described above.
One line with integers. The -th integer describes the current state of light L_i, where means off and means on.
For each test case, output a single integer: the minimum number of switch flips required for Ryu to turn off all the lights. If it is impossible, output the string impossible.
In the first example below, flipping switch S_4 followed by S_7 will turn off all the lights.
Example 1