AT_k2pc001_h3 お気に入りの数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$ 输入为一个整数 $n$。请输出最小操作次数。 如果不存在这样的方案，输出 $-1$。 如果没有任何操作被允许，则即使不进行任何操作，也视为“已经经过所有允许的转移方式至少一次”。 - $2 \leq n \leq 10^{12}$

一个整数 $n$。

如果存在满足条件的方案，输出最小操作次数；否则输出 $-1$。

由 ChatGPT 4.1 翻译