9 Numbers

source: 21st PC Koshien, Final

raw_problem:
９つの数字

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

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

隣接する上下左右のどれかの数字へカーソルを移動する。

カーソルが指し示す数字を入力する。

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

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

入力

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

$N$

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

出力

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

入出力例

入力例１

123456789

出力例１

17

入力例２

325821642813

出力例２

26

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

source: aizu

question:
Nine Numbers

![image](1.png)

At the entrance of PCK-kun's house, there is a special electronic lock. On this electronic lock, numbers from 1 to 9 are arranged in three vertical rows and three horizontal columns as shown in the figure on the right. There is a single cursor on the electronic lock that always points to one of the numbers.

To unlock the electronic lock, a predetermined sequence of numbers is set as the passcode. The lock can be opened by sequentially entering the numbers included in the passcode from left to right. When entering, consider either of the following as one operation:

- Move the cursor to any of the adjacent numbers above, below, left, or right.
- Enter the number that the cursor is pointing to.

When starting to enter the passcode, the cursor is pointing to the number at the bottom right as shown by the arrow in the figure. The numbers from 1 to 9 can be freely rearranged before starting the operation. PCK-kun wants to know how few the necessary number of operations to input the passcode can be by rearranging the numbers.

Create a program to find the minimum number of operations required to enter the passcode when it is given.

Input

The input is given in the following format:

$N$

On one line, the integer $N$ representing the passcode ($1 \leq N < 10^{10^5}$) is given. However, the digit 0 is not included in any of the digits of $N$.

Output

Output the minimum number of operations.

Input/Output Examples

Input example 1

123456789

Output example 1

17

Input example 2

325821642813

Output example 2

26

For example, if the numbers are rearranged as below, the passcode can be entered in 26 operations.

![image](2.png)

image_tags: Others Others

data_split: test