factorialCount

A factorial number is such a number that can be written as k! and is equal to the product of all integers 1 through k. For example, 4! = 1 * 2 * 3 * 4 = 24.

Any positive integer can be expressed as a sum of factorial numbers. Let the factorial count of a number n be defined as the minimum number of factorial numbers required to result in a sum of n.

Given a positive integer n, return its factorial count.

Example

• For n = 8, the output should be FactorialCount(n) = 2.
  The factorial count of 8 is 2, because 8 = 3! + 2! = 6 + 2.

• For n = 145, the output should be FactorialCount(n) = 3.
  The factorial count of 145 is 3, because 145 = 5! + 4! + 1! = 120 + 24 + 1.

Input/Output

• [execution time limit] 0.5 seconds

• [input] integer n

  Constraints:
  
  1 ≤ n ≤ 4 · 106.

• [output] integer

  • The factorial count of n.