A - Chess

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

En un tablero de ajedrez de 5 por 5 se colocan 12 caballos negros y 12 blancos, quedando una casilla vacía. En cada movimiento un caballo puede ocupar la casilla vacía siempre que ese se mueva como lo hacen los caballos en el ajedrez. Dada la configuración inicial del tablero, la pregunta es: cuál es la menor cantidad de movimientos en el que se puede alcanzar la siguiente configuración final.


Input

La primera línea de la entrada contiene un entero N (N < 14) que indica la cantidad de casos de prueba. Cada caso consiste d 5 líneas, cada una representando una fila del tablero. Las posiciones ocupadas por caballos blancos contienen 0 y las de caballos negros con 1 , la posición vacía está representada por un espacio.

No hay línea en blanco entre los casos de pueba.


Output

Por cada caso su tarea es encontrar la mínima cantidad de movimientos que lleva de la configuración inicial a la final. Si ese número es mayor que 10 imprima la oración “ Unsolvable in less than 11 move(s) ” en otro caso imprima “ Solvable in n move(s) ” donde n <= 10. La salida para cada caso deberá estar un una línea como se muestra en el ejemplo.

Sample test(s)

Input
2 01011 110 1 01110 01010 00100 10110 01 11 10111 01001 00000
Output
Unsolvable in less than 11 move(s). Solvable in 7 move(s).

Hints

El primer caso corresponde a esta configuración: