AT_abc407_c [ABC407C] Security 2

AtCoder 社の入口には特殊なパスコード入力装置があり、 この装置は文字列を $ 1 $ つ表示する画面と $ 2 $ つのボタンからなります。 画面に表示される文字列を $ t $ とします。 $ t $ ははじめ空文字列であり、ボタンを押すことで $ t $ に以下の変化が起きます。 - **ボタン A** を押すと、 $ t $ の末尾に `0` が追加される。 - **ボタン B** を押すと、 $ t $ に含まれるすべての数字が、それぞれ次の数字に置き換わる。ここで、`0` から `8` までの数字については次の数字は $ 1 $ 大きな数を表す数字とし、`9` の次の数字は `0` とする。 たとえば、 $ t $ が `1984` のときにボタン A を押すと $ t $ は `19840` に変化し、さらにボタン B を押すと $ t $ は `20951` に変化します。 文字列 $ S $ が与えられます。 $ t $ が空文字列である状態からボタンを $ 0 $ 回以上押して $ t $ を $ S $ に一致させるとき、ボタンを最少で何回押す必要があるかを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ S $

答えを出力せよ。

### Sample Explanation 1 以下の順にボタンを押せば、 $ t $ が `21` になります。 1. ボタン A を押す。 $ t $ は `0` になる。 2. ボタン B を押す。 $ t $ は `1` になる。 3. ボタン A を押す。 $ t $ は `10` になる。 4. ボタン B を押す。 $ t $ は `21` になる。 $ 4 $ 回より少ない回数ボタンを押して $ t $ を `21` にすることはできないので、 $ 4 $ を出力します。 ### Constraints - $ S $ は `0`, `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9` からなる文字列 - $ 1 \leq |S| \leq 5 \times 10^5 $ ( $ |S| $ は $ S $ の長さをあらわす)