Note: This is just the translation of "10664 - easy 8 Puzzles" in English. Please submit your code to "10664 - easy 8 Puzzles".
Given a 3×3 board with 9 tiles and every tile has one number from 0 to 8.
| 1 | 2 | 3 |
| 4 | 0 | 5 |
| 7 | 8 | 6 |
We can swap ‘0’ with its four adjacent (left, right, above, and below) tiles. For example:
step 1 : swap 0 with ‘5’
| 1 | 2 | 3 |
| 4 | 5 | 0 |
| 7 | 8 | 6 |
step 2 : swap 0 with ‘6’
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 0 |
The objective is to place the numbers on tiles to match the following configuration.
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 0 |
(Noting important in this paragraph, something like Rody is too busy and needs your help to solve this problem.)
Given T (1<=T<=30) in the first line, saying that there will be T test cases.
From 2nd line to (T+1)-th line, each line contains 9 distinct integers from 0 to 8, representing an 8-puzzle game. Nice integers will be filled to the 3×3 board in a row-major manner. For example, 1 2 3 4 0 5 7 8 6 will become the configuration as shown in the following figure.
| 1 | 2 | 3 |
| 4 | 0 | 5 |
| 7 | 8 | 6 |
For each 8-puzzle game, if it can be solved in 14 steps, print out "You can solve it within x steps.", x is the minimum number of steps to solve this puzzle. Otherwise, print out "You'd better skip this game.