有一块电量为n的充电宝，她计划给若干块电池充电，每次充电时会有一定电量的损失，使用电量ai时，其损失电量为f(ai)，f(x)表示除x以外最大因子。注意：若只充电1点，其损失电量也为1。

应该如何分配用光电量，使得损失总量最小。

输入格式

输入一个正数表示总电量n

输出格式

输出最小损失电量

输入样例1

4

输出样例1

2

输入样例2

9

输出样例2

2

说明提示

2≤n≤2×10⁹

限制

时间限制：1000ms，内存限制：256MiB