beecrowd | 2032

Game of Eight

By Gabriel Duarte, UNIFESO BR Brazil

Timelimit: 5

João is a boy who loves to play with logic games, he spends several hours of your day solving puzzles.
Currently the game that he's spending more time playing is the Sliding Puzzle, also known as Game of Eight, in which he has at hand a tray of 3 rows and 3 columns where each element of this board has a number or a blank space.

The object of the game is simple, given a scrambled board (Figure 1), João should leave it ordered (Figure 2) and the only movement possible to solve the problem is to move a number to the blank space.
Solve the toy is not a problem for João, he's already doing it without difficulty, but he was intrigued to know what is the minimum number of moves needed to solve.


Figure 1 - Figure 2


What you need to do to help João in his curiosity is simple, it will give you the initial configuration of the board and you should show, if any, the least amount of possible steps to solve the toy and what steps are needed to find the solution.
But there is one detail, João is a very methodical kid, so when he is playing and there are several possibilities at any given time it uses the following priority to set the move:
1) Move the piece that is on the blank space
2) Move the piece that is under the blank space
3) Move the piece that is on the right of the blank space
4) Move the piece that is on the left of the blank space
You must use the same priority to solve the problem.

Input

The input consists of several test cases, each case will have 3 lines each with 3 numbers 0-8, where zero represents the blank space. Assume that the toy is always scrambled.
The entry ends with the end of the file.

Output

For each test case print the message "Quantidade minima de passos = X", where X is the total required, followed by the steps made to resolve, each step must be separated by a blank line. if you can't solve the problem print: "Problema sem solucao".

Input Sample Output Sample

123
456
078

Quantidade minima de passos = 2
123
456
708


123
456
780