Problem Description

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

Input

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

Output

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

Sample Input

2

25608

24027

Sample Output

7680

16016

/****************************

数论欧拉函数：对正整数 n ，小于等于n的数中与n 互质的数的个数

参考一个前辈的笔记算是对欧拉函数初步了解：http://blog.csdn.net/mbxc816/article/details/7214872

****************************/

Code:

#include <iostream>

using namespace std;

int Euler(int x)// 求 欧拉函数值 其实就是通式的应用

{

    int i,res = x;

    for(i = 2;i*i<=x;i++)  //

    {

        if(x%i==0)

            res = res/i*(i-1);

        while(x%i==0)  //保证遍历的一定是质因子

            x/=i;

    }

    if(x>1)

        res = res / x*(x-1);// x 若为1，则所有质因子全部遍历，不为1 则表示最后一个质因子残余，继续res / x*(x-1)

    return res;

}

int main()

{

    int t,n;

    cin>>t;

    while(t--)

    {

        cin>>n;

        cout<<Euler(n)<<endl;

    }

    return 0;

}