Migrated from Lutece 2354 You know nothing, Jon Snow

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Ygritte and Jon are heading South to the Wall. Jon are described as "know nothing" for several times on this trip. Ygritte wants to confirm once again whether Jon know things, so an idea comes to her mind : given an integer N,and mark $A_i$ as the smallest divisor of N (not including 1), then N minus $A_i$ will be the new N. Repeat this operation until N is 0. Now Ygritte wants to know that how many times will this operation be performed for a given N.

Of course Jon knows nothing, but you know things for sure.

Input

An integer N（$2 \leq N \leq 10^{12}$）

Output

An integer represent how many times this operation will be performed.

Samples

4

2

998244353

1

10000009

4999994

Resources

电子科技大学第十届ACM趣味程序设计竞赛