题目描述

题目译自 XXXII Olimpiada Informatyczna – I etap Zamek cykliczny

Bajtynka 收到了 Bajtazar 送给她的生日礼物——一个逻辑玩具，叫做循环锁。循环锁由两个按钮和一个显示屏组成。显示屏上可以显示任意大小的十进制数字，不含前导零。起始显示的数字由玩具软件设定。

游戏目标是使显示的数字变成 $1$。为此可以使用两个按钮。按下第一个按钮，数字增加 $1$。按下第二个按钮，循环地将数字的十进制表示右移一位，使得最高位数字移动到最低位，然后移除所有前导零。

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

现在，Bajtynka 想知道需要按下最少次数的按钮来解决这个谜题。你的任务是计算出这个次数。

输入格式

输入的第一行包含一个数字 $n$ $(1 \leq n \leq 10^{1000000})$，表示当前显示的数字。

输出格式

输出一个数字，表示解决这个谜题所需的最少按钮按压次数。

301

17

要在 $17$ 次操作内解决这个谜题，应依次进行如下操作：

1. 按下第一个按钮 $8$ 次，此时玩具显示 $309$，
2. 按下第二个按钮，此时玩具显示 $93$，
3. 按下第一个按钮 $7$ 次，此时玩具显示 $100$，
4. 按下第二个按钮，此时谜题解决。

样例 2

见附加文件下 [zam1ocen.in](file:zam1ocen.in) 和 [zam1ocen.out](file:zam1ocen.out)。

该样例满足 $n=1000000$；答案是 $1$。

样例 3

见附加文件下 [zam2ocen.in](file:zam2ocen.in) 和 [zam2ocen.out](file:zam2ocen.out)。

该样例满足 $n=9908$；答案是 $6$。

样例 4

见附加文件下 [zam3ocen.in](file:zam3ocen.in) 和 [zam3ocen.out](file:zam3ocen.out)。

该样例满足 $n=9 \cdot 10^{999}$；答案是 $3$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$n \leq 100000$	$15$
$2$	数字 $n$ 的十进制表示仅包含 $0$ 和 $1$	$20$
$3$	$n \leq 10^{1000}$	$30$
$4$	无附加限制	$35$