Problem Description

Given a $3 \times 3$ grid, each cell contains a number, and all numbers in the grid are distinct. In each step, we may choose any $2 \times 2$ sub-square and rotate it clockwise, for example:

1 2 3
4 5 6
7 8 9

If we rotate the top-right $2 \times 2$ sub-square, we get:

1 5 2
4 6 3
7 8 9

Find the minimum number of steps needed to rotate the given state into

1 2 3
4 5 6
7 8 9

Input Format

The first line contains an integer $T$, the number of queries.

Then follow $T$ queries.

Each query consists of three lines, each containing three numbers, describing the current state of the $3 \times 3$ grid.

Output Format

Output $T$ lines. Each line contains one integer, the answer for that query.

2
1 2 3
4 5 6
7 8 9
1 5 2
4 6 3
7 8 9

0
3

Hint

For $60\%$ of the testdata, $T = 1$.
For all testdata, $T \le 10^5$.

Translated by ChatGPT 5