Bajtynka 在生日时收到了 Bajtazar 送的一件新逻辑玩具——循环锁。循环锁由两个按钮和一个显示屏组成。显示屏可以显示任意大的十进制数，且不含前导零。初始时，显示屏上显示的数字由玩具的程序选定。

游戏的目标是使显示屏上显示的数字变为 $1$。为此，可以使用上述两个按钮。按下第一个按钮，数字加 $1$。第二个按钮将数字的十进制表示循环左移一位，即最高位移至最低位，随后删除所有前导零。

例如，按下第一个按钮后，数字 $99$ 变为 $100$。按下第二个按钮后，数字 $143$ 变为 $431$，而数字 $700523$ 变为 $5237$。

现在 Bajtynka 想知道，解决这个谜题所需的最少按键次数是多少。你的任务是求出这个数字。

输入格式

输入的第一行也是唯一一行包含一个整数 $n$，表示当前显示的数字 ($1 \le n \le 10^{1\,000\,000}$)。

输出格式

你的程序应输出一个整数，表示解决谜题所需的最少按键次数。

样例

样例输入 1

301

样例输出 1

17

说明

解决该谜题需要 17 次操作，步骤如下： 1. 按下第一个按钮 8 次；此时玩具显示 309。 2. 按下第二个按钮；此时玩具显示 93。 3. 按下第一个按钮 7 次；此时玩具显示 100。 4. 按下第二个按钮，解决谜题。

子任务