题目描述

又一次世界末日即将来临！这次的罪魁祸首是 Julya 部落的日历。

这个部落的海狸们非常擅长数学。考古学家 Smart Beaver 得到了一块刻有神秘整数的圣盘。古海狸文的翻译如下：

“愿伟大的海狸保佑你！愿你的 chacres 得以开启，愿你的第三只眼永不因直视真理而失明！取下这个魔法数字，从中减去一个数字（这个数字必须在原数中出现），得到一个新的魔法数字。重复这个操作，直到魔法数字变为零。大地将在三只海狸的支撑下，存续的时间等于你执行减法的次数！”

显然，不同的减法序列可能会得到不同的操作次数。但 Smart Beaver 已经做好了最坏的打算，他想知道将魔法数字变为零所需的最少操作次数。

输入格式

输入仅一行，包含一个魔法整数 $n$，$0 \leq n$。

• 若要获得 20 分，需要满足约束条件：$n \leq 10^{6}$（子任务 C1）；
• 若要获得 40 分，需要满足约束条件：$n \leq 10^{12}$（子任务 C1+C2）；
• 若要获得 100 分，需要满足约束条件：$n \leq 10^{18}$（子任务 C1+C2+C3）。

输出格式

输出一个整数，表示将魔法数字变为零所需的最少减法次数。

说明/提示

在第一个测试样例中，最少操作次数的减法序列如下：

$24 \to 20 \to 18 \to 10 \to 9 \to 0$。

由 ChatGPT 4.1 翻译

样例

24

5