Solve the Puzzle

Given a grid containing numbers 1, 2, 3, …, 9, you are asked to perform a sequence of swap operations to obtain the following grid:

On each move, you can swap two neighbors (neighbors in either horizontal or vertical directions). What would be the minimum number of moves required to obtain the required grid?

1

2

3

4

5

6

7

8

9

Input

The input contains 3 lines each one containing 3 numbers representing the initial grid.

Output

The program should print the minimum number of moves required to obtain the 1, 2, 3, …, 9 grid.

Examples

Input

Output

2 1 3 7 5 9 8 4 6

4

Constraints

Time limit: 50 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue