팩토리얼의 합

양의 정수 $N$의 팩토리얼은 $N!$으로 적고, $N$보다 작거나 같은 모든 양의 정수의 곱으로 정의한다. 예를 들어 $4! = 4 \times 3 \times 2 \times 1 = 24$이다.

양의 정수 $N$이 주어진다. $N = a_1! + a_2! + \cdots + a_k!$를 만족하는 가장 작은 $k$를 구하는 프로그램을 작성하라. 각 $a_i$는 양의 정수이고, 같은 값이 여러 번 나와도 된다.

$N = 10$이면 답은 3이다. $10 = 3! + 2! + 2!$로 팩토리얼 세 개의 합으로 쓸 수 있다. $N = 25$이면 답은 2이다. $25 = 4! + 1!$이다.

첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 10^5$)

합이 $N$이 되는 팩토리얼의 최소 개수를 한 줄에 출력한다.