题目描述

在一个 $3\times 3$ 的九宫格上，摆放着标有 $1$ 至 $8$ 的八个滑块，剩下一个空格用 $0$ 表示。空格相邻的滑块可以滑入空格。

给定一种初始布局（初始状态）和目标布局（$123804765$），求从初始状态到目标状态的最少移动步数。

输入格式

输入初始状态，一行九个数字，空格用 $0$ 表示。

输出格式

输出一行一个整数，表示从初始状态到目标状态所需的最少移动步数。保证输入的状态一定能到达目标状态。

样例

283104765

4

提示

样例解释

样例中从初始状态到目标状态的一种方案共需 $4$ 步，且可以证明不存在更优的策略。