#include<stdio.h>
#include<math.h>
#define NMAX 100000
#define DMAX (NMAX>>4)+1
long long phi,cx,x;
long n;
unsigned char p[DMAX];


void read()
{
scanf("%lld",&x);
cx=x;
}

void ciur()
{
long i,j,lim;
lim=sqrt(NMAX)+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<=NMAX;j=j+(i<<1)+1)
            {
             p[j>>3]=p[j>>3] | (1<<(j&7));
            }
      }
}

void calcphi()
{
phi=2*x;
long long lim;
lim=sqrt(2*x);
lim=lim>>8;
long long B,b,d;
if (x%2==0)
   {phi=phi/2;
    while (x%2==0)
           x/=2;
    }
for (B=1;B<=lim && x>1;B++)
    for (b=0;b<=7 && x>1;b++)
        {
         if (!(p[x>>3] & (1<<(x&7))))
            {
             phi=phi/x*(x-1);
             return;
            }
         if (!(p[B] & (1<<b)))
            {d=((B<<3)+b)<<1+1;
            if (x%d==0)
              {
               phi=phi/d;
               phi=phi*(d-1);
               while (x%d==0)
                     {
                      x/=d;
                     }
              }
              
             }
         }

if (x>1)
   {
    phi=phi/x;
    phi=phi*(x-1);
   }
}

void suma()
{
long long s=cx;
s=s*phi;
printf("%lld\n",s);
}


int main()
{
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
scanf("%ld",&n);
long i;
ciur();
for (i=1;i<=n;i++)
    {
     read();
     calcphi();
     suma();
    }
return 0;
}