← 返回题目列表

AtCoder · k2pc001_e5

E. 最喜欢的号码 2

中文机器翻译题面 查看原题

問題文

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} 可达到的数量上限

入力例 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

(故事)kyuridenamida
(问题)kyuridenamida
(测试仪)fura2