题目描述

卫宫士郎正在和 Saber 进行魔术训练，面前是一块3×3的魔术阵盘。阵盘上摆放八枚印有编号1~8的魔力刻印碎片，还有一处魔力空缺位，以数字 0 标记。

空缺位上下左右相邻的刻印碎片，可以借着魔术回路的流转，和空位交换位置，就像士郎那出名的跳高操作一样，碎片 “跳” 到空位上。 圣杯给出了指定的阵盘目标排布：123804765。士郎需要调整阵盘，让布局和圣杯的要求一致。 请帮士郎算出，让阵盘到达目标状态所需要的最少跳跃次数。保证输入一定存在可行方案。

输入格式

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

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

输入输出样例 #1

283104765

4

说明/提示

样例解释

图中展示了样例当中从初始状态到目标状态的一种方案，共需要 $4$ 步。

并且可以证明，不存在更优的策略。

Limitation

1s, 1024KiB for each test case.