The factorial of a positive integer number N, denoted as N!, is defined as the product of all positive integernumberssmallerorequaltoN. Forexample4!=4×3×2×1=24. Given a positive integer number N, you have to write a program to determine the smallest number k so that N = a1! + a2! + . . . + ak!, where every ai, for 1 ≤ i ≤ k, is a positive integer number. Input The input consists of several test cases. A test case is composed of a single line, containing one integer number N (1 ≤ N ≤ 105). Output For each test case in the output your program must output the smallest quantity of factorial numbers whose sum is equal to N. Sample Input 10 25 Sample Output 3 2