#include<stdio.h>
#include<math.h>
#define NMAX 100001
#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));
}
void afisare(long n)
{
long i;
for(i=1;2*i+1<=n;++i)
   if(!(p[i>>3]&(1<<(i&7))))
		printf("%ld ",2*i+1);
}

long long phi(long n)
{
long j=1,c,lim,k,x,e,o;
long long s;
e=n;  c=0;  lim=sqrt(n)+1; x=n;
while((n&1)==0)
  {  c=1;
	 n=(n>>1);
  }
if(c>0)
  e=(e>>1);
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);    o=((n-1)>>1);
	   if(!(p[o>>3]&(1<<(o&7))))
			 break;
	 }
   ++j;
 }
if(n>1)
   e=e/n*(n-1);
s=((long long)x*e)<<1;
return s;
}
int main()
{
long n,x,i;
long long u;
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
scanf("%ld",&n);
ciur(NMAX);
//afisare(1000);

for(i=1;i<=n;++i)
{
scanf("%ld",&x);
u=phi(x);
printf("%lld\n",u);

}
return 0;
}