algo2017_week1_euler

#include<bits/stdc++.h>
using namespace std;

int Pow(long long x, int n, long long mod) {
    long long Ans = 1, t = x;
    while(n) {
        if(n&1)
            Ans *= t, Ans %= mod;
        t *= t, t %= mod, n >>= 1;
    }
    return (int)Ans;
}

int isPrime(int n) {
    if(n == 2 || n == 3)    return 1;
    if(n == 1)    return 0;
    if(!(n & 1))    return 0;
    int a, x, flag = 1, t;
    for(a = 0; a < 2; a++) {
        x = rand() % (n - 4) + 2;
        t = Pow( x , n-1 , n );
        if(t != 1)    return 0;
    }
    return 1;
}

int gcd(int a,int b){
    while((a%=b)&&(b%=a));
    return a+b;
}

int euler( int n ){
    int t = 0;
    if( n == 1 ) return 1;
    if( isPrime( n ) ) return n - 1;
    for( int i = 1 ; i <= n ; i++ ){
        if( gcd( i , n ) == 1 ) ++t;
    }
    return t;
}

int main(){
    int n , t;
    scanf("%d",&t);
    while( t-- ){
        scanf("%d",&n);
        printf("%d\n" , euler(n));
    }
    return 0;
}