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

unordered_set<int> PRI;

void getPrimes(int x){
    for(int i=2; i<=x/i; ++i){
        while(x%i==0){
            PRI.insert(i);
            x/=i;
        }
    }
    if(x>1) PRI.insert(x);
}

int main(){
    // 公式法计算欧拉函数
    int n;
    cin>>n;
    int x;
    while(n--){
        PRI.clear();
        cin>>x;
        getPrimes(x);
        int res=x;
        for(auto &p: PRI){
            res=res*(1.0-1.0/p);
        }
        cout<<res<<endl;
    }

    return 0;
}