There are black and white knights on a 5 X 5 chessboard. There are twelve knights of each color, and there is one square that is empty. At any time, a knight can move into an empty square as long as it moves like a knight in normal chess.
Given an initial position of the board, the question is: what is the minimum number of moves in which we can reach the final position which is shown in the picture.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case contains five lines; each line represents one row of a chessboard. The positions occupied by white knights are marked by 0 and the positions occupied by black knights are marked by 1. The space corresponds to the empty square on the board.
Output
For each case, print the case number and the minimum number of moves leading from the starting input configuration to the final one. If that number is bigger than 15, then output one line stating Unsolvable in less than 16 move(s). otherwise output one line stating Solvable in n move(s). where n ≤ 15.
Sample
| Sample Input | Sample Output |
|---|---|
2 01011 110 1 01110 01010 00100 10110 01 11 10111 01001 00000 | Case 1: Unsolvable in less than 16 move(s). Case 2: Solvable in 7 move(s). |
Notes
The first set of the sample input corresponds to the following configuration:
