#P2618. 数字工程

数字工程

题目描述

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

可采用的方法有:

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

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

请问把 nn 变成 11 最少需要消耗多少能量?

输入格式

本题有多组数据。

对于每组测试,一行一个整数 nn

输出格式

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

1
4
0
2

提示

1n1061 \le n \le 10^6