#include<stdio.h>
#include<math.h>
char ciur[50010];


void ciurul()
{
long n=100000;
ciur[0]=1;
long lim=sqrt(n);
long i,j;
for(i=1;2*i+1<=lim;i++)
  if(ciur[i]==0)
	 for(j=2*i*i+2*i;2*j+1<=n;j=j+2*i+1)
		ciur[j]=1;
}


long long phi(long n)
{
long long phi;

if(ciur[(n-1)>>1]==0 && (n&1))
  return 2*(long long)(n-1)*n;
phi=n;
long cn=n,e=0;
long i;
long lim=sqrt(n)+1;
while((n&1)==0)
  {
  e++;
  n=n>>1;
  }
if(e)
  phi=phi/2;
for(i=1;2*i+1<=lim && n>1;i++)
  if(ciur[i]==0)
	 {
	 e=0;
	 while(n%(2*i+1)==0)
		{
		e++;
		n=n/(2*i+1);
		}
	 if(e)
		{
		phi=phi/(2*i+1)*2*i;
		}
	 if(ciur[(n-1)>>1]==0)
		{
		phi=phi/n*(n-1);
		n=1;
		break;
		}
	 }
if(n>1)
  phi=phi/n*(n-1);
return (long long)2*cn*phi;
}


void read()
{
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
long n,x;
scanf("%ld",&n);
long i;
for(i=1;i<=n;i++)
  {
  scanf("%ld",&x);
  printf("%lld\n",phi(x));
  }
}


int main()
{
ciurul();
read();
return 0;
}