#include<stdio.h>
long long int  n,k,d,m,i,k1;
int main()
{
FILE *f,*g;
f=fopen("sum.in","r");
g=fopen("sum.out","W");
fscanf(f,"%lld",&n);
for(i=1;i<=n;i++)
{ 
	fscanf(f,"%lld",&k);
	d=2;m=k;k1=k;
	if(m%d==0)
		{
		while(m%d==0)m/=d;
		k/=d;
		k*=d-1;
		}
	for(d=3;d*d<=m;d=d+2)
		if(m%d==0)
			{
			while(m%d==0)m/=d;
			k/=d;
			k*=d-1;
			}
	if(m>1)
		{k/=m;k*=m-1;}
	k1*=k;
	fprintf(g,"%lld",k1);
	return 0;
}