给你一个整数$$$n$$$。对其应用以下算法:
1. 如果$$$n = 0$$$,则结束算法;
2. 求$$$n$$$的最小素因数$$$d$$$;
3. 从 $$$n$$$ 中减去 $$$d$$$ 并转到步骤 $$$1$$$。
确定算法将进行的减法次数。
输入
唯一一行包含单个整数 $$$n$$$ ($$$2 \le n \le 10^{10}$$$)。
输出
打印一个整数 — 算法将进行的减法次数。
示例
输入 #1
5
输出 #1
1
输入 #2
4
输出 #2
2
注意
在第一个示例中 $$$5$$$ 是最小的素因数,因此它会立即被减去以得到 $$$0$$$。
在第二个示例中,$$$2$$$ 是两个步骤中的最小素因数。