C - お気に入りの数2(Favorite Number2)

Time Limit: 1 sec / Memory Limit: 256 MB

問題文

※20:31現在, この問題もセット採点がうまく動作していないようです。修正後リジャッジを行います。(恐らくテストケース毎に表示されている結果は正しいです)。ご迷惑をおかけします。

※20:35セット採点データを修正し、リジャッジを行いました。正解しているように見えた解答も不正解扱いになっている可能性があります。ご確認ください。ご迷惑をおかけしました。

2 以上 n 以下の正整数 x に対して, 以下の操作が許されている.

  • x+1n 以下のとき, 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
入力では, 整数 n1 つだけ与えられる.

出力

最小となる操作回数を出力せよ.
もし, そのような方法が存在しない場合は-1を出力せよ.
もしどのような操作も許されていない場合, 一切操作を行わなくても "この操作で許される全ての遷移の仕方を, 少なくともそれぞれ 1 回ずつ以上行った", とみなしてよい.

制約

  • 2 ≦n ≦ 10^{12} たどり着ける数の上限値

入力例 1

9

出力例 1

10
許された遷移の仕方は 9 つあり, 以下の通りである.
  • 2→3
  • 3→4
  • 4→5
  • 5→6
  • 6→7
  • 7→8
  • 8→9
  • 4→2
  • 9→3
これらを少なくとも1回以上行って, x=2 として終了するのに必要な最小操作回数は 10 回である.

入力例 2

5

出力例 2

-1

入力例 3

4

出力例 3

3

(Story) kyuridenamida
(Problem) kyuridenamida
(Tester) fura2