URI Online Judge | 1936
# Factorial

**Timelimit: 1**

By Vinícius Fernandes dos Santos Brazil

The factor of a positive integer N, denoted by N!, is defined as the product of the positive integers smaller than or equal to N. For example 4! = 4 × 3 × 2 × 1 = 24.

Given a positive integer N, you should write a program to determine the smallest number k such that N = a_{1}! + A_{2}! + ... + A* _{k}*!, where each a

For example, for N = 10 the answer is 3, it is possible to write N as the sum of three numbers factor: 10 = 3! + 2! + 2!. For N = 25 the answer is 2, it is possible to write N as the sum of two factorial numbers: 25 = 4! + 1!.

The input consists of a single line containing an integer **N** (1 ≤ **N** ≤ 10^{5}).

Its program should produce a single line with an integer representing the smallest amount of factor numbers whose sum is equal to the value of **N**.

Input Samples | Output Samples |

10 |
3 |

25 |
2 |