AT_k2pc001_e5.お気に入りの数2(Favorite Number2)

对于 $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$ 开始，想要以最少的操作次数，经过所有允许的转移方式（每种转移方式至少各经过一次），并最终回到 $x=2$。
你的任务是判断是否存在这样的方案，如果存在，请输出最小的操作次数；如果不存在，则输出 $-1$。
如果没有任何操作是允许的，即使一项操作都不做，也视为“已经经过了所有允许的转移方式至少一次”。

输入仅包含一个整数 $n$。

输出最小的操作次数。如果不存在这样的方案，输出 $-1$。

• $2 \leq n \leq 10^{12}$

示例：

9

10

5

-1

4

3

由 ChatGPT 4.1 翻译