Description

你将会获得一个数n,按照以下的算法进行：

1、 如果n==0,就结束这个算法，否则转步骤二。

2、 找到n的因子中是最小素数d。

3、 n减去d,并且转到步骤1。

输出这个算法中减去数字的次数。

Format

Input

数字n的范围（2≤n≤10000000000）

Output

输出这个的算法减去数字的次数。

Samples

5

1

Hint