Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Como todos sabemos Fito es un gran fanático de la Facultad de Matemática y Computación (MATCOM) de la Universidad de la Habana. Él siempre está pidiendo ayuda a los estudiantes, pero esta vez nos quiere ayudar. Lo que quiere hacer es prender las luces de los pasillos de la Facultad para que podamos estudiar por la noche. El problema consiste en que prender las luces de la Facultad es complicado, es por esto que no se hace normalmente. Cada lámpara tiene un interruptor que, como si fuera poco, cambia el estado de ella, de las $D$ anteriores y de las $D$ siguientes en caso de existir. La cuestión es que Fito quiere prender todas las luces pero sin formar mucho alboroto para que los custodios de la Universidad no le llamen la atención, así que quiere hacerlo utilizando la menor cantidad de veces los interruptores.

Input

La primera línea contiene un entero que representa la cantidad de casos que Fito va a resolver. En cada caso habrá un entero $n$ $(1 \le n \le 100)$ y otro $D$ $(0 \le D \le 15)$, que representan la cantidad de luces y el valor $D$ mencionado en el problema. La segunda línea tendrá $n$ enteros que representan los estados de cada una de las lámparas (1 significa encendida y 0 apagada).

Output

La salida debe contener un entero por cada caso que representa la respuesta de Fito, o la palabra " impossible " (sin las comillas) si Fito no pudo haber resuelto el problema.

Sample test(s)