숫자 1을 가장 좋아하는 교원이는 1이 아닌 숫자 n을 자신의 능력을 동원해서
1로 바꾸기를 즐겨한다. 교원이는 다음의 세 가지 능력을 가지고 있다.
|
n이 2로 나누어떨어지면 2로 나눈다.
n이 5로 나누어떨어지면 5로 나눈다.
n에서 1을 뺀다.
|
숫자 n을 1로 만들기 위한 교원이의 능력 사용 최소 횟수를 알려주는 프로그램을 작성하시오.
예를 들어, n이 10일 때 10 → 5 → 4 → 2 → 1 로 4번 만에 1이 될 수도 있고, 10 → 2 → 1로 2번 만에 1이 될 수도 있다. 따라서 능력을 사용하는 최소 횟수는 2이다.
입력예시1)
2
출력예시1)
1