#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll n=1000000;
vector v;
ll arr[n]={0};
arr[0]=arr[1]=1;
for(ll i=2;i<n;i++)
{
if(arr[i]==0)
{
v.push_back(i);
for(ll j=(i*i);j<n;j=j+i)
{
arr[j]=1;
}
}
}
int t;
cin>>t;
while(t--)
{
int a,e;
cin>>a;
e=a;
vector<int> b;
vector<int>::iterator it;
int c=int(sqrt(a));
int i=0;
while(a!=1)
{
if(a%v[i]==0)
{
b.push_back(v[i]);
a=a/v[i];
while(a%v[i]!=0)
{
a=a/v[i];
}
}
if(i<v.size())
{
i++;
}
if(v[i]>c)
{
b.push_back(a);
a=1;
break;
}
}
long long int ans=1,num=1,d=1;
for(it=b.begin();it!=b.end();it++)
{
int p=*it;
num=num*((*it)-1);
d=(d*(p));
ans=(e*num)/d;
num=1;
d=1;
}
//cout<<","<<num<<","<<d<<endl;
//ans=(e*num)/d;
cout<<ans<<endl;
}
return 0;
}