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

- 如果x+1<=n，x+1可变为新的x
- 如果sqrt(x)为整数， sqrt(x)可变为新的x

注：sqrt是cmath库的开根号函数，sqrt(4) = 2

例如x=2时，新的x可以为3，x=4时，新的x可以为（2，5）中任意一个。

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

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

第一行：一个整数n

50%的数据：2<=n<=3000。

100%的数据：2<=n<=10^{12}(任意时刻x都不能超过的上限值)

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

所有允许的操作共有9个，如下:
2→3
3→4
4→5
5→6
6→7
7→8
8→9
4→2
9→3
将以上操作都至少执行一遍，以x=2时的最小操作次数为10，操作过程依次如下:
2→3
3→4
4→5
5→6
6→7
7→8
8→9
9→3
3→4
4→2

wms