The 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 way it will not take long before Ryu is spotted by a guard. To remain unseen, Ryu will need to turn off all the lights as quickly as possible. The hallway contains a sequence of \textbf{n} lights \textbf{L_1}...\textbf{L_n}. Some of these lights are turned on. Destroy-ing the lights with his shurikens would be too loud, so he needs to turn them off the old-fashioned way, using light switches. Luckily, there is a switch box nearby with a light switch \textbf{S_i} for every light \textbf{L_i}. However, after trying one of the switches, he notices something funny. When he ips the switch \textbf{S_i}, it does not only turn on/off light \textbf{L_i}, but also some of the neighboring lights. Ryu notices that there is a parameter \textbf{D} such that ipping switch \textbf{S_i} turns on/off all the lights \textbf{L_\{i-D\}}...\textbf{L_\{i+D\}}, if they exist (This means that \textbf{S_1} turns on/off all the lights \textbf{L_1}...\textbf{L_\{D+1\}} and \textbf{S_n} turns on/off all the lights \textbf{L_\{n-D\}}...\textbf{L_n}. Of course, if \textbf{D} ≥ \textbf{n}, then \textbf{L_\{D+1\}} and \textbf{L_\{n-D\}} will not exist either.). Turning on or off lights can attract the attention of the guards, so Ryu would like to turn off all the lights with the minimum number of times flipping a switch. Can you help him out? \InputFile The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format: \begin{itemize} \item One line with two integers \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}) and \textbf{D} (\textbf{0} ≤ \textbf{D} ≤ \textbf{15}): the number of lights and the parameter mentioned above. \item One line with \textbf{n} integers. The \textbf{i}^th integer describes the current state of light \textbf{L_i}, where \textbf{0} means off and \textbf{1} means on. \end{itemize} \OutputFile For every test case in the input, the output should contain one integer on a single line: the minimum number of times Ryu needs to flip a switch to turn off all the lights. If it is impossible to turn off all the lights, then output the string "\textbf{impossible}" instead. \textbf{Example} In the first example below, flipping switch \textbf{S_4} followed by \textbf{S_7} will turn off all the lights.