#include<stdio.h>
#include<iostream.h>
#include<math.h>
#define DMAX 50010//62501
char p[DMAX];
void ciur(long n)
{
long i,j,lim;
lim=sqrt(n)+1;
for(i=1;2*i+1<=lim;++i)
  if(p[i]==0)
    for(j=2*i*i+2*i;2*j+1<=n;j=j+2*i+1)
        p[j]=1;
}
long phi(long n)
{
long j=1,c,lim,k,x;
long long e;
e=n;  c=0;  lim=sqrt(n)+1; x=n;
while(n%2==0)
  {  c=1;
     n=n/2;
  }
if(c>0)
  e=e/2;
while(2*j+1<=lim && n>1)
 {
   if(p[j]==0)
     { c=0;
       k=2*j+1;
       while(n%k==0)
          { c=1;
            n=n/k;
          }
       if(c>0)
         e=e/k*(k-1);
     }
   ++j;
 }
if(n>1)
   e=e/n*(n-1);
e=2*x*e;
return e;
}
int main()
{
long n,x,i;
long long u;
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
cin>>n;
for(i=1;i<=n;++i)
{
cin>>x;
u=phi(x);
cout<<u<<'\n';

}
fcloseall();
return 0;
}