Sum of Factorials

The factorial of a positive integer $N$ is written $N!$ and is defined as the product of every positive integer that is at most $N$. For example, $4! = 4 \times 3 \times 2 \times 1 = 24$.

You are given a positive integer $N$. Write a program that finds the smallest $k$ such that $N = a_1! + a_2! + \cdots + a_k!$. Each $a_i$ is a positive integer, and the same value may appear more than once.

For $N = 10$ the answer is 3, because $10 = 3! + 2! + 2!$ writes $N$ as a sum of three factorials. For $N = 25$ the answer is 2, because $25 = 4! + 1!$.

The first line contains an integer $N$ ($1 \le N \le 10^5$).

Print on one line the smallest number of factorials whose sum equals $N$.