#include<iostream>
using namespace std;
int main()
{
    int n,m,i,ans;
    scanf("%d",&n);
    while(n--){
        scanf("%d",&m);
        ans=m;
        for(i=2;i<=m/i;i++)
            if(m%i==0){
                ans=ans/i*(i-1);
                while(m%i==0)m/=i;
            }
        if(m>1)ans=ans/m*(m-1);
        printf("%d\n",ans);
    }
    return 0;
}