在圆上一点S，扔出一个球，这个球经过若干次反弹还有可能回到S点。N = 4时，有4种扔法，如图：

 

恰好经过4次反弹回到起点S（从S到T1，以及反向，共4种）。

给出一个数N，求有多少种不同的扔法，使得球恰好经过N次反弹，回到原点，并且在第N次反弹之前，球从未经过S点。

Input

输入一个数N(1 <= N <= 10^9)。

Output

输出方案数量。

Input示例

4

Output示例

4 思路：球反弹n次回到原来的点 所以整个圆被分成 n+1 份 　　　假设 球弹出时一次跨过 a 条边 也就是 a 份等弧 　　　只有当 gcd(a,n+1)==1 时 球可以弹n次返回起点 　　　证明并不会 好像画几个正多边形 这个规律 可以看出来 　　　于是成了 求phi(n+1)

1 #include 
        
          2 #include 
         
           3  4 int phi(int n) { 5     int Ans=n; 6     for(int i=2; i*i<=n; ++i) { 7         if(n%i==0) { 8             Ans-=Ans/i; 9             while(!(n%i)) n/=i;10         }11     }12     if(n>1) Ans-=Ans/n;13     return Ans;14 }15 16 int hh() {17     int n;18     scanf("%d",&n); 19     20     printf("%d\n",phi(n+1));    21     return 0;22 }23 24 int sb=hh();25 int main(int argc,char**argv) {;}