An 8 Puzzle is played in a board of 3 by 3. The board contains all the integers from 1 to 8 and an empty space, and initially they can be at any configuration. Your goal is to make your board look like the following board:
In each move, you are allowed to move any cell adjacent to the space cell. The moves are described in the following section:
Input
Input starts with an integer T (≤ 1000), denoting the number of test cases.
Each case starts with a blank line. The next three lines will contain three integers each. You may assume that the given board is valid. The space cell will be marked as 0.
Output
For each case, print the case number and the minimum number of moves required to reach the goal state. If it's impossible, then print impossible.
Sample
| Sample Input | Sample Output |
|---|---|
3 1 2 3 4 5 6 8 7 0 1 2 3 4 5 6 7 0 8 1 3 2 4 6 5 7 8 0 | Case 1: impossible Case 2: 1 Case 3: 18 |