Factorial
By Vinícius Fernandes dos Santos 
Brazil
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 = a1! + A2! + ... + Ak!, where each ai, for 1 ≤ i ≤ k is a positive integer.
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 ≤ 105).
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 |