팩토리얼은 급격히 증가하므로 13 ! 만 해도 32 비트 컴퓨터에서 정수 표현범위를 넘어가고 70! 은 실수범위를 넘어간다.

수 N 을 입력으로 받아 N! 의 결과 중 오른쪽에서 왼쪽으로 영이 아닌 최초의 수를 구하는 것이 문제이다.

예를 들면,

• 5! = 1 * 2 * 3 * 4 * 5 = 120 이므로 2 가 답이고 ,
• 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040 이므로 4 가 답이다.

입력

출력

입출력 예

입력

7

출력

4

출처:usaco