600126 - 最短路++

Time Limit

1000 毫秒

Memory Limit

128 MB

通过次数

6

提交次数

26

在一个3×3的矩阵上,0-89个数字,其中数字0可以和上下左右相邻的数字交换位置,但其他数字之间不可以交换位置;例如01、02之间可以交换位置12、68之间不可以。给出矩阵初始状态,求出矩阵达到目标状态123804765最少需要多少次交换?

注:矩阵状态用一行连续连续数字表示,每3个数字依次表示第一行从左到右、第二行从左到右、第三行从左到右的数字,例如目标状态123804765在矩阵中为:

123

804

765

Input

一行,由0-8这9个数字构成,表示矩阵当前状态。

Output

达到目标状态所需的最少交换次数。

Examples

Input

283104765

Output

4