描述

在一个 $3\times 3$ 的棋盘上，放着数字 $1\sim 8$ 以及一个空格（用 $0$ 表示）。任意时刻，你可以把空格与它上、下、左、右相邻的一个数字交换位置（如果相邻位置在棋盘外，则不能交换）。

给定一个 $3\times 3$ 的初始局面，请你求出最少经过多少次移动，才能到达下面的目标局面：

$$\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 0 \end{matrix} $$

如果初始局面无论如何也无法到达目标局面，请输出 $-1$。

输入格式

输入共一行，是一个由 $9$ 个数字组成的字符串（无空格）。每个字符是 0–8 中的一个，且这 $9$ 个数字恰好各出现一次。

约定按行展开成一个长度为 $9$ 的字符串：例如目标局面表示为 123456780，而样例 2 表示为 123456708，对应：

$$\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 0 & 8 \end{matrix} $$

输出格式

输出一行一个整数，表示从初始局面到目标局面的最少移动次数。如果无解，输出 -1。

样例

样例输入 1

123456780

样例输出 1

0

样例输入 2

123456708

样例输出 2

1

样例输入 3

123746508

样例输出 3

5