又一场世界末日即将来临!这次的罪魁祸首就是朱利亚部落的历法。
这个部落的海狸非常了解数学。聪明的海狸是一位考古学家,他得到了一个神圣的盘子,上面有一个神奇的整数。 Old Beaverish 的翻译如下:
“愿伟大的海狸保佑你!愿你的查克斯张开,愿你的第三只眼睛永远不会因看到真相而失明!取出魔法数字,从中减去一个数字(该数字必须出现在数字中)并得到一个新的魔法数字。重复此操作,直到魔法数字等于零。地球将在三只海狸上停留一段时间,等于你执行减法的次数!”
不同的减法序列显然可以得到不同的运算次数。但聪明的海狸已准备好面对最坏的情况,并要求您计算他将幻数减少到零所需的最少操作次数。
输入
单行包含幻数 n,0 ≤ n。
- 要得到20分,需要解决有约束的问题:n ≤ 106(子问题C1);
- 要得到40分,需要解决有约束的问题:n ≤ 1012(子问题C1+C2);
- 要获得 100 分,您需要解决具有约束条件的问题:n ≤ 1018(子问题 C1+C2+C3)。
输出
打印一个整数——将幻数变成零的最小减法次数。
示例
输入 #1
24
输出 #1
5
注意
在第一个测试样本中,可以通过以下减法序列达到最小操作数:
24 → 20 → 18 → 10 → 9 → 0