Divisor Subtraction

Description:

Input:

The only line contains a single integer $$$n$$$ ($$$2 \le n \le 10^{10}$$$).

Output:

Print a single integer — the number of subtractions the algorithm will make.

Sample Input:

5

Sample Output:

1

Sample Input:

4

Sample Output:

2

Note:

In the first example $$$5$$$ is the smallest prime divisor, thus it gets subtracted right away to make a $$$0$$$.

In the second example $$$2$$$ is the smallest prime divisor at both steps.