お気に入りの数2(Favorite Number2)
题意翻译
## 题目描述
对$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)$中的任意一个。
kagamiz想知道从$x=2$开始，将所有允许的操作都执行至少一遍，使$x$的值再次为$2$的方法中，操作次数最少的方法的操作次数。
你的任务就是判断这样的方法是否存在，如果存在，则输出最小操作次数。
## 输入
```
n
```
输入仅一个整数$n$。
## 输出
输出一行最小操作次数。
当不存在符合条件的方法时输出$-1$。
## 数据范围
- $2≤n≤10^{12}$ $($任意时刻$x$都不能超过的上限值。$)$
## 样例
### 输入1
```
9
```
### 输出1
```
10
```
所有允许的操作共有$9$个。如下：
- $2→3$
- $3→4$
- $4→5$
- $5→6$
- $6→7$
- $7→8$
- $8→9$
- $4→2$
- $9→3$
将以上操作都至少执行一遍，以$x=2$结尾的最小操作次数为$10$。
### 输入2
```
5
```
### 输出2
```
-1
```
### 输入3
```
4
```
### 输出3
```
3
```
感谢@ミク 提供的翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/k2pc-easy/tasks/k2pc001_e5
$ 2 $ 以上 $ n $ 以下の正整数 $ x $ に対して, 以下の操作が許されている.
- $ x+1 $ が$ n $ 以下のとき, $ x\ +\ 1 $ を新たな $ x $ とする.
- $ \sqrt{x} $ が整数のとき, $ \sqrt{x} $ を新たな $ x $ とする.
例えば, $ x\ =\ 2 $ のとき, $ 3 $を新しい $ x $ とすることができる.
$ x\ =\ 4 $ のとき, $ (2,5) $ のいずれかを新しい $ x $ とすることができる.
そこで, kagamizは $ x=2 $ として開始し, この操作で許される全ての遷移の仕方を, 少なくともそれぞれ $ 1 $ 回ずつ以上行って 再び $ x=2 $ に戻ってくるような方法のうち, 操作回数が最小になる場合にかかる操作回数を知りたい.
あなたの仕事は, そのような方法が存在するかどうかと, 存在するならばその最小操作回数をkagamizに教えてあげることである.
> $ n $
入力では, 整数 $ n $ が $ 1 $ つだけ与えられる. 最小となる操作回数を出力せよ.
もし, そのような方法が存在しない場合は`-1`を出力せよ.
もしどのような操作も許されていない場合, 一切操作を行わなくても "この操作で許される全ての遷移の仕方を, 少なくともそれぞれ $ 1 $ 回ずつ以上行った", とみなしてよい. - $ 2\ ≦n\ ≦\ 10^{12} $ たどり着ける数の上限値
```
9
```
```
10
```
```
5
```
```
-1
```
```
4
```
```
3
```