#include<stdio.h>  
#include<iostream.h>  
#include<math.h>  
#define NMAX 1000000  
#define DMAX (NMAX>>4)+1  
char p[DMAX];  
void ciur(long n)  
{  
long i,j,lim;  
lim=sqrt(n)+1;  
for(i=1;(i<<1)+1<=lim;++i)  
  if(!(p[i>>3]&(1<<(i&7))))  
    for(j=((i*i)<<1)+(i<<1);(j<<1)+1<=n;j=j+(i<<1)+1)  
        p[j>>3]=p[j>>3]|(1<<(j&7));  
}  
  
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((j<<1)+1<=lim && n>1)  
 {  
   if(!(p[j>>3]&(1<<(j&7))))
     { c=0;  
       k=(j<<1)+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=(x*e)<<1;  
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;  
}