数字工程

题目描述

ACM 实验室开启了一个数字工程项目，希望把正整数 n 通过一些特殊方法变成 1。

可采用的方法有：

1. 减去 1
2. 除以它的任意一个素因子。

每操作一次消耗一个单位的能量。

请问把 n 变成 1 最少需要消耗多少能量？

输入

本题有多组数据。

对于每组测试，一行一个整数 n。

输出

一行一个整数，表示最少消耗的能量。

样例

提示

1 \le n \le 10^6。

来源

luogu