数字工程

题目描述

ACM 实验室开启了一个数字工程项目,希望把正整数 $n$ 通过一些特殊方法变成 $1$。 可采用的方法有: 1. 减去 $1$ 2. 除以它的任意一个素因子。 每操作一次消耗一个单位的能量。 请问把 $n$ 变成 $1$ 最少需要消耗多少能量?

输入输出格式

输入格式


**本题有多组数据。** 对于每组测试,一行一个整数 $n$。

输出格式


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

输入输出样例

输入样例 #1

1
4

输出样例 #1

0
2

说明

$1 \le n \le 10^6$。