fate_fibo

프로그램 명: fate_fibo

제한시간: 1 초

피보나치 수열 F[n]의 정의는 다음과 같다.

F[1]=1, F[2]=1 일 때, F[n]=F[n-1]+F[n-2]

각각의 항들을 더하여 10^k 보다 작되, 더해지는 서로 다른 항의 갯수의 최댓값을 구하는 것이 목적이다. ** 같은 항을 여러번 더할 수 있다 **

예를 들어 k=1 일때를 보면,

등으로 많은 조합이 나올 수 있지만, 사용되는 항의 최대 갯수는 4개를 넘을 수 없다.

입력으로 k가 주어질 때, 사용할 수 있는 항의 최대 갯수를 출력하시오.

k가 주어진다. (0 <= k <= 1000)

서로 다른 항의 최대 갯수를 출력하시오.

입력

1

출력

4

입력

13

출력

61

출처:FATE