3898 - 数字工程
时间限制 : 1 秒
内存限制 : 128 MB
ACM 实验室开启了一个数字工程项目，希望把正整数 n 通过一些特殊方法变成 1。
可采用的方法有：
- 减去 1
- 除以它的任意一个素因子。
每操作一次消耗一个单位的能量。
请问把 n 变成 1 最少需要消耗多少能量？
输入
本题有多组数据。
对于每组测试，一行一个整数 n。
输出
一行一个整数，表示最少消耗的能量。
样例
输入
1 4
输出
0 2
提示
1 \le n \le 10^6。
来源
luogu