Server Time: Tue Nov 19, 2019 9:49 am
Welcome ( logout
1139 - 8 Puzzle
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

An 8 Puzzle is played in a board of 3 by 3. Initially the board is scattered. Your goal is to make your board to the following board:

1 2 3

4 5 6

7 8 0

Here 0 denotes the blank. The moves are described in the following section:

1 2 3                1 2 3                1 2 0                1 0 2                1 6 2

4 0 6       ->     4 6 0       ->     4 6 3       ->     4 6 3    ->        4 0 3

7 8 5                7 8 5                7 8 5                7 8 5                7 8 5

Initial               right                   up                   left                 down

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.

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 Input

Output for Sample Input

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

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan