Contest Duration: - (local time) (100 minutes) Back to Home
B - Factorial Yen Coin /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \leq P \leq 10^7
• P は整数である。

### 入力

P


### 入力例 1

9


### 出力例 1

3


1! = 1 円硬貨、2! = 2 円硬貨、3! = 6 円硬貨を 1 枚ずつ使うと 3 枚の硬貨で 9 円の商品をちょうどの金額で支払うことができます。これより少ない枚数で支払う方法は存在しません。

### 入力例 2

119


### 出力例 2

10


1! 円硬貨を 1 枚、2! 円硬貨を 2 枚、3! 円硬貨を 3 枚、4! 円硬貨を 4 枚使えばよいです。

### 入力例 3

10000000


### 出力例 3

24


Score : 200 points

### Problem Statement

The coins used in the Kingdom of Takahashi are 1!-yen coins, 2!-yen coins, \dots, and 10!-yen coins. Here, N! = 1 \times 2 \times \dots \times N.

Takahashi has 100 of every kind of coin, and he is going to buy a product worth P yen by giving the exact amount without receiving change.

We can prove that there is always such a way to make payment.

At least how many coins does he need to use in his payment?

### Constraints

• 1 \leq P \leq 10^7
• P is an integer.

### Input

Input is given from Standard Input in the following format:

P


### Output

Print the minimum number of coins needed.

### Sample Input 1

9


### Sample Output 1

3


By giving one (1! =) 1-yen coin, one (2! =) 2-yen coin, and one (3! =) 6-yen coin, we can make the exact payment for the product worth 9 yen. There is no way to pay this amount using fewer coins.

### Sample Input 2

119


### Sample Output 2

10


We should use one 1!-yen coin, two 2!-yen coins, three 3!-yen coins, and four 4!-yen coins.

### Sample Input 3

10000000


### Sample Output 3

24