旋转谜题

题目描述

育华学校举办了一场别开生面的数学趣味挑战活动，其中有一个有趣的项目是关于九宫格的旋转问题。活动现场给出一个 $3×3$ 的九宫格，每个格子里都填有一个独特的数字（即九个格子里的数字互不相同）。在这个挑战中，同学们每一步可以选择九宫格内任意一个 $2×2$ 的区域，将其按照顺时针方向进行旋转。

例如，初始的九宫格状态为：

1 2 3
4 5 6
7 8 9

当选择旋转其右上角的 $2×2$ 区域时，就会得到新的九宫格状态：

1 5 2
4 6 3
7 8 9

现在，同学们面临的挑战是：对于给定的不同九宫格初始状态，计算最少需要经过多少步这样的旋转操作，才能将其变换为目标状态：

1 2 3
4 5 6
7 8 9

输入格式

输入的第一行包含一个整数 $T$ ，它代表了本次数学趣味挑战中询问的组数。也就是说，会有 $T$ 个不同的九宫格初始状态需要同学们去分析和计算。

接下来依次输入每组询问的具体内容。每组询问都由三行组成，每行包含三个数，这三个数依次表示对应行九宫格格子里的数字，描述了当前询问的九宫格的具体状态。

输出格式

根据输入的 $T$ 组询问，输出 $T$ 行结果。每一行都包含一个整数，这个整数表示对于本次询问所对应的九宫格初始状态，最少需要进行的旋转操作步数，以达到目标九宫格状态。

输入输出样例 #1

输入 #1

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

输出 #1

0
3

说明/提示

1. 部分数据情况：对于 $60\%$ 的评测用例，询问的组数 $T = 1$ 。这意味着在这部分测试数据中，只需要处理一个九宫格的初始状态。
2. 全部数据范围：对于所有的评测用例，询问的组数 $T$ 满足 $T \leq 10^5$ 。也就是说，在整个育华学校的数学趣味挑战活动的评测中，最多会有 $10^5$ 个不同的九宫格初始状态需要进行分析和计算旋转步数。