欧拉函数

//HDU 1286
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<algorithm>
using namespace std;
#define N 1010
#define INF 0x3f3f3f3f

int solve(int n)
{
    int ans=n;

    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0)
        {
            ans=ans*(i-1)/i;
            while(n%i==0)
            {
                n/=i;
            }
        }
    }
    if(n>1)
        ans=ans*(n-1)/n;
    return ans;
}

int main()
{
    int T, n, ans;
    scanf("%d", &T);

    while(T--)
    {
        scanf("%d", &n);
        ans=solve(n);
        printf("%d
", ans);
    }
    return 0;
}