У нас є монети номіналом \(1!, 2!, \dots 10!\). Відомо, що \(N! = 1 \times 2 \times \dots \times N\).

Всього є 100 монет кожного виду, і треба оплатити продукт вартістю P без здачі.

Можна довести, що такий спосіб оплати завжди є.

Знайдіть мінімальну кількість монет, яку треба використати для оплати?

Формат вхідних даних

Вхідний потік містить ціле число \(P\) (\(1 \le P \le 10^7\))

Формат вихідних даних

У вихідний потік виведіть шукану кількість монет.

Примітка

До прикладу 1:

Одна (1! =1) монета, одна (2! = 2) та одна (3! = 6).

Неможливо сплатити цю суму, використовуючи менше монет.

Приклад вхідних даних

9

Приклад вихідних даних

3

Приклад вхідних даних

119

Приклад вихідних даних

10

Приклад вхідних даних

10000000

Приклад вихідних даних

24