题目描述

牛宝宝生活在一个有着奇怪纳税制度的国家，他必须缴纳的税额计算方式为：假设牛宝宝的总收入为$n$，则税额等于$n$的最大因子$k$ $（k<n）$。

比如，$n=6$时，$k$为$3$，若$n$为质数，则$k$为$1$。

牛宝宝是个喜欢投机取巧的人，他打算把他的收入拆成几份，分开缴税，使总税额最少。

现在告诉你牛宝宝的总收入，需要你算出最少需要交多少税。

输入格式

输入一个数表示牛宝宝的工资n$(1 \le n \le 10^{18})$

输出格式

输出最少交的税的金额

4

2