上海保卫战
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 257 M，其他语言514 M
64bit IO Format: %lld

题目描述

小M从不开火，是他的弹药与民主的讨论后自行决定发射。
冻肉小L在超级上海保卫战的时候看到了小M的轨道像是定向制导一样落下命中光能族，于是绞尽脑汁想出了一个很妙的轨道高爆弹火力网选址方法。他兴致勃勃的上传真理部，但是真理部告诉他只有证明出他选址方法的正确性并且复杂度够低才算真正的皿煮。这可难坏了小L，于是小L拿着这个函数找到了你...

函数描述：
 函数的输入只有一个整数 n ， 共三个步骤。
 1、如果是 n = 0，则函数将结束；
 2、否则 找出 n 的最小质除数 p ；
 3、从 n 中减去 p，返回步骤 1 进行下一轮 ;

由于小L的俺寻思之力爆棚，易得出了函数的正确性，你只需要测试这个函数的复杂度，即需要知道他会运行多少轮才能结束。

输入描述:

唯一一行包含一个整数 n ( 1 < n < 1010)

输出描述:

输出一个整数 x ：函数的运行次数。
示例1

输入

复制 
5

输出

复制 
2

说明

第一轮 n = 5 的最小质除数是5，返回 0 到达第二轮第一步。
第二轮 n = 0，满足结束条件，退出函数。
因此输出 2 。

示例2

输入

复制 
4

输出

复制 
3

备注:

函数哪怕只运行一步也算运行了一轮