题目描述

在神奇的算术王国里，居民们使用一种基于阶乘的奇特货币系统。王国使用的硬币有 $1!$ 元硬币、 $2!$ 元硬币、 $\dots$ 和 $10!$ 元硬币。在这里， $N! = 1 \times 2 \times \dots \times N$ 。每个面值都对应着一种独特的“算术币”。

算术王国的居民都非常富有，他们中的很多人都收藏了从1!到10!的每种算术币多枚。其中居民$Lily$，每种硬币都拥有 $100$个 ，她选中了一个价值为P单位的珍贵宝物，并计划使用她收藏的算术币来支付这个价值，而且要做到支付的总额恰好等于宝物的价值，不多也不少。

$Lily$想要知道，为了购买这件宝物，她至少需要动用多少枚算术币。

幸运的是，王国的算术法则保证了无论P是多少，她总能找到一种支付方式。

输入格式

输入是一个整数P，代表$Lily$想要购买的宝物的价值

• $1 \leq P \leq 10^7$
• $P$ 是整数

输出格式

输出一个整数，表示$Lily$为了支付价值P单位的宝物，至少需要动用多少枚算术币。

9

3

样例1解释

通过提供一枚 $1!$ 元硬币、一枚 $2!$ 元硬币和一枚 $3!$ 元硬币，我们可以支付 $1+2+6=9$ 元。

119

10

样例2解释

我们应该使用一枚 $1!$ 元硬币、两枚 $2!$ 元硬币、三枚 $3!$ 元硬币和四枚 $4!$ 元硬币。$（1*1+2*2+3*6+4*24=119）$

10000000

24