005 - ９つの数字

問題

PCK君の家の入口には特殊な電子錠がついている。この電子錠には１から９までの数字が、右の図のように縦３行、横３列に配置されている。この電子錠には数字を指し示すカーソルが１つあり、カーソルによって常にどれか１つの数字が指し示されている。

電子錠を開錠するために、所定の数字列が暗証番号として設定されている。暗証番号に含まれる数字を左から順番に入力していくことで開錠することができる。入力するときには、以下のどちらも１回の操作と考える。

• 隣接する上下左右のどれかの数字へカーソルを移動する。
• カーソルが指し示す数字を入力する。

暗証番号の入力開始時には、図のように矢印で表されるカーソルが右下の数字を指している。１から９までの数字は、操作開始前に自由に並べ替えることができる。PCK君は、数字を並べ替えることによって、暗証番号を入力するために必要な操作回数がどれだけ少なくできるかを知りたい。

暗証番号が与えられたとき、暗証番号を入力するために必要な操作回数の最小値を求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$

１行に暗証番号を表す整数$N$ ($1 \leq N < 10^{10^5}$)が与えられる。ただし、$N$の各桁に0は含まれない。

出力

操作回数の最小値を出力する。

入出力例

入力例１

123456789

出力例１

17

入力例２

325821642813

出力例２

26

たとえば、以下のように数字を並べ替えれば、26回の操作で暗証番号を入力できる。