题目描述

在 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\ \leq\ P\ \leq\ 10^7$
• $P$ 是整数。