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 翻译