문제

양의 정수 이 주어질 때, 아래 연산을 최소 몇 번 반복해야 이 되는지 출력하세요.

• 을 나누는 가장 작은 소수를 라고 할 때, 을 로 바꾼다.

예로, 였다면, 2번의 연산을 한 뒤에는 이 된다.

입력

첫째 줄에 양의 정수 이 주어진다.

출력

최소 몇 번의 연산을 적용해야 이 되는지 출력한다.