#include<bits/stdc++.h>
using namespace std;
long long sub1(long long n){
    long long res=0;
    for (long long i=1;i<=n;++i){
        if (__gcd(i,n)==1) res++;
    }
    return res;
}
long long sub2(long long n){
    long long t=1;
    long long c=n;
    for (long long i=2;i*i<=n;++i){
        if (n%i==0){
            t*=i;
            c*=(i-1);
            while (n%i==0) n/=i;
        }
    }
    if (n!=1){
        c*=(n-1);
        t*=n;
    }
    return c/t;
}
int main(){
    int test;
    ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	freopen("UOC.INP", "r", stdin);
	freopen("UOC.OUT", "w", stdout);
    cin>>test;
    while (test--){
        long long n;
        cin>>n;
        //long long dem1=sub1(n);
        long long dem2=sub2(n);
        cout<<dem2<<"\n";
    }
}
