Problem Description

We send a light from one point on a mirror material circle,it reflects N times and return the original point firstly.Your task is calcuate the number of schemes.![](../../data/images/C628-1004-1.jpg)

 

 

Input

First line contains a single integer T(T≤10) which denotes the number of test cases. For each test case, there is an positive integer N(N≤106).

 

 

Output

For each case, output the answer.

 

 

Sample Input

1 4

 

 

Sample Output

4

 

 

Source

 

 

对应中文题目

问题描述

从镜面材质的圆上一点发出一道光线反射NNN次后首次回到起点。 问本质不同的发射的方案数。

输入描述

第一行一个整数T，表示数据组数。T≤10T \leq 10T≤10 对于每一个组，共一行，包含一个整数，表示正整数N(1≤N≤106)N(1 \leq N \leq 10^{6})N(1≤N≤106)。

输出描述

对于每一个组，输出共一行，包含一个整数，表示答案。

输入样例

14

输出样例

4 来自官方题解

 

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 #include
            
              7 using namespace std; 8 #define ll long long 9 ll n;10 ll eular(ll n)11 {12 ll res=1;13 for(ll i=2;i*i<=n;i++)14 {15 if(n%i==0)16 {17 n/=i,res*=i-1;18 while(n%i==0)19 {20 n/=i;21 res*=i;22 }23 }24 }25 if(n>1) res*=n-1;26 return res;27 }28 int main()29 {30 int t;31 scanf("%d",&t);32 while(t--){33 scanf("%I64d",&n);34 ll ans=eular(n+1);35 printf("%I64d\n",ans);36 }37 return 0;38 }