我们现在纸上画一个方框，平均分成n份，编号为1~n，然后呢，我们从1号开始移动k个数字，如果遇上边界就改变方向，就是下面的样子，比如8个格子，移动两个数字

 

1->3->5->7->7->5->3->1->3....如果这样一直跳，就会出现死循环，不能把每一个格子都踩中，那么我们需要最小的k是多少时才能满足每一个格子都踩中呢？

“那不是等于1么”学长脱口而出~

这样就没法玩了，难怪都这么久都没有女朋友，当然k不能等于1！

 

 

输入

输入n表示划分n个格子

2<=n<=10⁵

 

输出

输出最小的k满足每一个格子都踩中

k不等于1

 

样例输入

8

样例输出

3

提示

 

提示 1->4->7->6->3->2->5->8 全部踩中 HDU 1222 http://www.acmerblog.com/hdu-1222-Wolf-and-Rabbit-1585.html

　http://acm.hdu.edu.cn/showproblem.php?pid=1222

1 #include 
      
        2 #include 
       
           // C++头文件，C++完全兼容C 3 #include 
        
           // C++头文件，C++完全兼容C 4 #define fre  freopen("out.txt","w",stdout)   //以文件代替控制台输入，比赛时很常用，能缩短输入测试样例的时间 5 using namespace std;  // C++头文件，C++完全兼容C 6  7 int ans,n,k; 8  9 int main()10 {11     while(cin>>n)12     {13         for(int i=2; i<=2*n; i++)14         {15             if(__gcd(2*n-2,i)==1)16             {17                 cout<
         <