问题描述

给定一个 $3\times 3$ 的网格，其由 $1\sim 8$ 和一个 x 构成。

例如：

1 2 3
4 x 6
7 5 8

我们可以将 x 与其上、下、左、右四个方向之一的数字互换位置（如果存在）。

我们目的是通过交换，使得网格变成如下格式（也可以称作标准格式）：

1 2 3
4 5 6
7 8 x

例如示例的交换过程为：

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

现在给定你一个初始网格，请你求出得到标准格式的最少交换次数，如果不存在可行解，则输出 $-1$。

输入格式

输入一行，表示初始网格。

例如：

用 1 2 3 4 x 6 7 5 8 表示：

1 2 3
4 x 6
7 5 8

输出格式

输出一个整数，表示最少交换此时，如果不存在可行解，则输出 -1。

样例输入

1 3 x 2 5 8 4 7 6

样例输出

16