题目描述

对 $2$ 以上（包括 $2$）$n$ 以下（包括 $n$）的正整数 $x$ 可以进行以下操作：

• 如果 $x+1 \le n$，$x+1$ 可变为新的 $x$
• 如果 $\sqrt{x}$ 为整数，$\sqrt{x}$ 可变为新的 $x$

例如 $x=2$ 时，新的 $x$ 可以为 $3$。$x=4$ 时，新的 $x$ 可以为 $(2, 5)$ 中的任意一个。

kagamiz 想知道从 $x=2$ 开始，将所有允许的操作都执行至少一遍，使 $x$ 的值再次为 $2$ 的方法中，操作次数最少的方法的操作次数。

你的任务就是判断这样的方法是否存在。如果存在，则输出最小操作次数。

输入格式

输入 $1$ 行，$1$ 个整数 $n$。

输出格式

输出 $1$ 行最小操作次数。当不存在符合条件的方法时输出 -1 。

样例 #1

样例输入 #1

9

样例输出 #1

10

样例 #2

样例输入 #2

5

样例输出 #2

-1

样例 #3

样例输入 #3

1000000

样例输出 #3

333333999

提示

样例 1 说明：

所有允许的操作共有 $9$ 个，如下：

$2\to 3$

$3\to 4$

$4\to 5$

$5\to 6$

$6\to 7$

$7\to 8$

$8\to 9$

$4\to 2$

$9\to 3$

将以上操作都至少执行一遍，使得 $x = 2$ 时的最小操作次数为 $10$，操作过程依次如下：

$2\to 3$

$3\to 4$

$4\to 5$

$5\to 6$

$6\to 7$

$7\to 8$

$8\to 9$

$9 \to 3$

$3 \to 4$

$4\to 2$

数据范围

对于 $50\%$ 的数据，$2\le n\le 3\times 10^3$

对于 $100\%$ 的数据，$2 \le n \le 3\times 10^{12}$ (任意时刻 都不能超过的上限值)。