Iroha와 Kaguya는 최근 정수에 기반한 수학 게임에 푹 빠졌다.

처음에는 두 사람이 양의 정수 $n$ 하나를 공유한다. 두 플레이어는 번갈아 연산을 수행하며, Iroha와 Kaguya가 각각 한 번씩 연산을 수행하는 것을 한 라운드로 정의한다. 각 라운드에서:

1. Iroha가 먼저 한다. 음이 아닌 정수 $x$ ($0\le x<n$)를 선택하고 현재 $n$을 $n+x$로 바꿔야 한다.

2. Kaguya가 두 번째로 한다. 현재 $n$을 나누는 소수 $p$ (즉 $p\mid n$)를 선택하고 현재 $n$을 $\frac{n}{p}$로 바꿔야 한다.

위 연산을 계속 반복한다. 어느 라운드든 끝난 뒤 $n=1$이면 게임은 즉시 끝난다.

게임 중 Iroha는 전체 라운드 수를 최대화하려고 하고, Kaguya는 전체 라운드 수를 최소화하려고 한다. 두 플레이어가 완전히 합리적이며 최적 전략을 사용한다고 가정할 때, 게임이 최종적으로 지속될 전체 라운드 수를 구하여라.

입력

첫 번째 줄에는 게임의 초기 수를 나타내는 정수 $n$ ($1\le n\le10^{18}$)이 주어진다.

출력

두 플레이어가 최적 전략으로 플레이할 때 게임이 지속되는 전체 라운드 수를 나타내는 정수 하나를 한 줄에 출력한다.

예제

입력 1

1

출력 1

0

입력 2

9

출력 2

4

입력 3

16

출력 3

5