该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

对2以上（包括2）n以下(包括n)的正整数x可以进行以下操作。

.如果x+1<=n,x+1可变为新的x

.如果 $\sqrt{x}$ 为整数，$\sqrt{x}$ 可变为新的X，

例如x=2时，新的x可以为3,x=4时，新的x可以为(2,5)中愿意的一个。

想知道从x等于2开始，将所有允许的操作都执行至少一遍，是x的值再次为2次数再少的方法的操作次数，你的任务就是判断这样的方法是否存在，如果存在输出再小的操作次数，不存在输出-1。

输入格式

输入1行，1个整数n。

输出格式

一行一个数，最小的操作次数。不存在输出-1。

样例 #1

样例输入 #1

9

样例输出 #1

10

样例 #2

样例输入 #2

5

样例输出 #2

-1

提示

样例1解释：

所有允许的操作共有9个，如下：

2—>3

3—>4

4—>5

5—>6

6—>7

7—>8

8—>9

4—>2

9—>3

这些操作至少一次，变为2最少要10次，如下：

2—>3

3—>4

4—>5

5—>6

6—>7

7—>8

8—>9

9—>3

3—>4

4—>2

样例2解释：没法变到2，输出-1。

50%的数据：$2 \le n \le3*10^{3}$

100%:$2 \le n \le10^{12}$