Eleven puzzle

Partychen invents a new game named “Eleven Puzzle” .Just like the classic game “Eight Puzzle”,but there some difference between them:The shape of the board is different and there are two empty tiles.

The tile in black means it’s empty

Each step you can move only one tile.
Here comes the problem.How many steps at least it required to done the game.

The first line of input contains one integer specifying the number of test cases to follow.
Every case contains five lines to describe the initial status of the board. 0 means empty.

It’s confirmed that the board is legal.

Output one line for each testcase.Contain an integer denotes the minimum step(s) it need to complete the game.Or “No solution!” if it’s impossible to complete the game within 20 steps.

3
2
1 0 3
4 5 6 7 8
9 0 11
10
0
1 2 3
4 5 6 7 8
9 10 11
0
0
11 10 9
8 7 6 5 4
3 2 1
0

2
0
No solution!

2009 Multi-University Training Contest 18 - Host by ECNU