题目描述

给定一个正整数$\red{n(2<=n<=10^{10})，}$按照如下流程操作：

$\red{1}$、如果$\red{n=0，}$结束；

$\red{2}$、找到$\red{n}$的最小质因子$\red{d}$；

$\red{3}$、$\red{n}$减去$\red{d}$并且返回步骤$\red{1}$

请问该流程中步骤$\red{3}$会执行多少次？

输入格式

共一行，一个整数$\red{n}$。

输出格式

一个整数，代表流程中步骤$\red{3}$执行次数。

样例

输入样例

5

输出样例

1

提示

对于$\red{50\%}$的数据，有$\red{2<=n<=10^7}$；

对于$\red{100\%}$的数据，有$\red{2<=n<=10^{10}}$。