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