该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

dash最近迷上了一个叫八数码的游戏，如下图 $1$，在 $3 \times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移动空格中。

游戏的目标是通过棋子的移动使 $8$ 个棋子到达图 $2$ 的布局。

在上面的图 $1$ 中，我们可以把 $5$ 向上移，然后再将 $8$ 向左移动后达成游戏目标变成图 $2$ 的布局，完成这局游戏最少需要 $2$ 步。

dash知道你是个编程高手，希望你编写一个程序计算完成每一局游戏的最少步数。

输入格式

第一行，一个整数 $n$，表示游戏的局数。

接下来的 $n$ 行，每行一个字符串，对应一个初始的游戏布局。（每个字符串中含有数字字符 $0\sim 8$ 各 $1$ 个， $0$ 表示空格，如图 $1$ 的布局可以记录为 $123406758$ ）

输出格式

$n$ 行，每行一个整数，代表每局游戏所需的最少步数。

注意，有的游戏初始布局，无论进行多少次操作也没有办法到达目标，此时请输出 $-1$。

样例

2
123406758
283104765

2
-1

解释#1

第一局：第 $1$ 步，将第三行的 $5$ 向上移动；第 $2$ 步，将第三行的 $8$ 向左移动就可以完成游戏；答案为 $2$。

第二局：这个布局无论进行多少次操作都没有办法达到游戏目标，输出 $-1$。

数据范围

$1\le n\le 10$