You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

考虑一个有 $3$ 行和 $3$ 列的网格。网格的每个单元格中都有一个整数。从 $1$ 到 $9$ （包括这两个整数）的每个整数在网格中恰好出现一次。

您可以对网格执行以下三种操作。

给定两个这样的网格，计算将第一个网格转换为第二个网格所需的最少操作次数。

输入格式

有多个测试用例。输入的第一行包含一个整数 $T$ ( $1 \le T \le 2 \times 10^5$ )，表示测试用例的数量。对于每个测试用例

对于前三行，每一行包含一个长度为 $3$ 的字符串，对于这三行中的第$i$行的字符串分别代表 $a_{i,1},a_{i,2},a_{i,3}$

在接下来的三行中， 每一行包含一个长度为 $3$ 的字符串，对于这三行中的第$i$行的字符串分别代表 $b_{i,1},b_{i,2},b_{i,3}$

输出格式

每个测试用例输出一行。如果可以将第一个网格转换为第二个网格，则输出一个整数，表示所需的最少操作数；如果无法转换，则输出 $-1$ 代替。

样例

输入

4
293
678
514
624
579
183
624
579
183
293
678
514
123
456
789
321
456
789
123
456
789
123
456
789

输出

3
5
-1
0

数据分布

$40\%$ 的样例，$T=2$ $100\%$的样例，$1 \le T \le 2*10^5$

时空限制

• 时间限制：$3s$
• 空间限制：$512M$