#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<<(i&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;
}