Iroha and Kaguya have recently become fascinated by a mathematical game based on integers.
Initially, they share a positive integer $n$. The two players take turns performing operations; a single round is defined as both Iroha and Kaguya completing one operation each. In each round:
Iroha goes first: She must choose a non-negative integer $x$ ($0\le x<n$) and replace the current $n$ with $n+x$.
Kaguya goes second: She must choose a prime number $p$ that divides the current $n$ (i.e., $p\mid n$) and replace the current $n$ with $\frac{n}{p}$.
The above operations repeat continuously. If $n=1$ after the end of any round, the game ends immediately.
During the game, Iroha aims to maximize the total number of rounds played, while Kaguya aims to minimize the total number of rounds. Assuming both players are perfectly rational and adopt optimal strategies, please determine the total number of rounds the game will ultimately last.
Input
The first line contains an integer $n$ ($1\le n\le10^{18}$), representing the initial number of the game.
Output
Output a single line containing an integer, representing the total number of rounds the game will last given that both players play optimally.
Examples
Input 1
1
Output 1
0
Input 2
9
Output 2
4
Input 3
16
Output 3
5