Problem Description
Oaiei likes playing games. He has created a new game recently.
The game is derived from the very famous game “eight puzzle”. It has nine blocks in the 3 * 3 matrix (three rows and three columns). The intial state is shown above.
There are two kinds of movement for oaiei to change the state:

a right rotation shifts one position to the right bottom block circularly.

a left rotation shifts one position to the left botton block circularly.
Now your task is to write a program, given a state, if the given state is solvable, you should find a way to set it to the intial state using the minimum possible number of moves; if the puzzle is unsolvable, you should output “No solution”.
Input
There are multiple test cases. For each test, there are three lines that describe a puzzle state. Each line consists of three integers, separated by a space. The nine integers are 19 respectively.
Output
For each test, if the given state is solvable,you should output an integer N, indicating the minimum number of moves required to set the puzzle to its initial state, if the puzzle is unsolvable, you should output “No solution”.
Sample Input
3 1 6
7 8 9
4 5 2
1 4 3
2 5 6
7 8 9
5 6 3
2 9 4
7 8 1
Sample Output
No solution
1
3
Source
FOJ月赛2008年10月