Minimum Rotations to Solve the 3x3 Grid

You are given a 3×3 grid, where each cell contains a distinct number. In one move, you can choose any 2×2 sub‐grid and rotate it clockwise. Formally, if the chosen sub‐grid is

[ \begin{bmatrix} a & b \ c & d \end{bmatrix} ]

after one clockwise rotation it becomes

[ \begin{bmatrix} c & a \ d & b \end{bmatrix} ]

For example, consider the grid

1 2 3
4 5 6
7 8 9

If we rotate the top‐right 2×2 sub‐grid (i.e. the sub‐grid containing 2, 3, 5, 6) clockwise, we obtain

1 5 2
4 6 3
7 8 9

The goal is to determine the minimum number of moves needed to transform a given grid into the target state

1 2 3
4 5 6
7 8 9

You can assume that the input state is always a permutation of the numbers in the target state and is reachable using the allowed moves.

inputFormat

The input consists of 3 lines, each containing 3 space-separated integers representing the starting grid.

outputFormat

Output a single integer denoting the minimum number of rotations required to reach the target grid.

sample

1 2 3
4 5 6
7 8 9

0