P10578 [Lanqiao Cup 2024 National A] Rotating 3×3 Grid

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: ```plain 1 2 3 4 5 6 7 8 9 ``` If we rotate the top-right $2 \times 2$ sub-square, we get: ```plain 1 5 2 4 6 3 7 8 9 ``` Find the minimum number of steps needed to rotate the given state into ```plain 1 2 3 4 5 6 7 8 9 ```

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 $T$ lines. Each line contains one integer, the answer for that query.

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