#include<stdio.h>
#include<math.h>
#define DMAX 50005
char p[DMAX];
long n,i;
long nr,cp,phi,lim;
long long sum;
void ciur(long N)
{
 long i,j,lim;
 lim=sqrt(N)+1;
 for(i=1;2*i+1<=lim;i++)
  if(p[i]==0)
   {
	for(j=2*i*i+2*i;2*j+1<=N;j=j+2*i+1)
	 p[j]=1;
   }
}
int main()
{
 freopen("sum.in","r",stdin);
 freopen("sum.out","w",stdout);
 ciur(50001);
 scanf("%ld",&nr);
 for(i=1;i<=nr;i++)
  {
   scanf("%ld",&n);
   cp=n;
   phi=n;
   if(n%2==0)
	{
	 while(n%2==0)
	  n=n/2;
	 phi=phi/2;
	}

   if(p[(n-1)/2]==0)
	phi=(phi/n)*(n-1);
   else
   {
	i=1;
	lim=sqrt(n);
	while(n>1 && 2*i+1<=lim)
	 {
	  if(p[i]==0)
	  {
	   if(n%(2*i+1)==0)
		{
		 while(n%(2*i+1)==0)
		  n=n/(2*i+1);
		 phi=phi/(2*i+1);
		 phi=phi*(2*i);
		}
	  }
	 i++;
	}
	if(n>1)
	  {
	   phi=phi/n;
	   phi=phi*(n-1);
	  }
	}//else
	sum=2*cp*phi;
	printf("%lld\n",sum);

   }
 return 0;
}