题目描述

在AtCoder国中，使用的硬币面值为1!元、2!元、...、10!元。这里，$N$! = 1 × 2 × ... × $N$。小高拥有每种面值的硬币各100枚，他要购买一件价值$P$元的商品，并且要支付准确金额而不需要找零。我们可以证明总是存在这样一种支付方式。小高至少需要使用多少枚硬币来完成支付？

输入格式

输入整数$P$

输出格式

输出所需的最少硬币数量。

样例

9

3

119

10

10000000

24

样例解释

【样例说明1】
通过给出一枚(1! =) 1元硬币、一枚(2! =) 2元硬币和一枚(3! =) 6元硬币，我们可以准确支付价值9元的商品。没有使用更少硬币数量的支付方式。

【样例说明2】
我们应该使用一枚1!元硬币、两枚2!元硬币、三枚3!元硬币和四枚4!元硬币。

数据范围

$1 ≤ P ≤ 10^7$, $P$是整数。

来源

• AtCoder ABC208B