新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。

Input

第一行是测试数据的组数CN（Case number，1<CN<10000），接着有CN行正整数N（1<n<32768），表示会员人数。

Output

对于每一个N，输出一行新朋友的人数，这样共有CN行输出。 

Sample Input

22560824027

Sample Output

768016016 // 辗转相除法求公约数

1 #include
      
        2  3 int cmd(int a, int b) 4 { 5     int t=1; 6     if(a
       
        1)23                 c++;24         printf("%d\n", n-c-1);25     }26     return 0;27 }
       
      

// 先打表求素数，用i遍历[2,N),用j遍历[2,i]. 寻找不大于i的素数j，判断其是否为i与N的公约数

1 #include
      
        2  3 int prime(int n) 4 { 5     int i, flag=1, k; 6     for(i=2; i*i<=n; i++) 7         if(n%i==0) 8         { flag=0; break; } 9     return flag;10 }11 12 int main()13 {14     int cn, n, c, i,j,flag, pri[32768]={
    0};15     for(i=2;i<=32767;i++)16         if(prime(i))17             pri[i]=1;18     scanf("%d", &cn);19     while(cn--)20     {21         c=0;22         scanf("%d", &n);23         for(i=2;i
      

// Compiler Error C2103：You cannot take the address of a register.

1 #include
      
        2 int main() 3 { 4     register int cn, n; 5     scanf("%d", &cn); 6     while(cn--) 7     { 8         scanf("%d", &n); 9         int a[32768]={
    0};10         for(register int i=2;i<=n/2;i++)11         {12             if(n%i==0)13                 for(register int j=1;i*j
      

// 若一个数是N除1以外的因子，那么它不超过N的倍数也是N的因子. // i找因子，j控制倍数，下标为会员号码. 只有新朋友的值为0.

1 #include
      
        2 int main() 3 { 4     int cn, n; 5     scanf("%d", &cn); 6     while(cn--) 7     { 8         scanf("%d", &n); 9         int a[32768]={
    0};10         for(int i=2;i<=n/2;i++)11         {12             if(n%i==0)13                 for(int j=1;i*j