#include<stdio.h>
#define N 100001
long n,m,i,j,k,x[10000],p[N],t,h[N];
char v[20],z[20];
unsigned long long y;
int main()
{freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
x[++k]=2;
for(i=1;((i*i)<<1)+(i<<1)<N;i++)       
if(!(p[i>>3]&(1<<(i&7)))) 
      for(j=((i*i)<<1)+(i<<1);(j<<1)+1<N;j+=(i<<1)+1) 
              p[j>>3]|=(1<<(j&7));
for(i=1;2*i+1<N;++i)  
if(!(p[i>>3]&(1<<(i&7)))) 
      x[++k]=2*i+1;
for(i=2;i<N;i++)
      {for(h[i]=j=i,t=1;x[t]*x[t]<=j&&j>1&&t<=k;t++)
      if(j%x[t]==0)
              {h[i]=(h[i]/x[t])*(x[t]-1);
              while(j%x[t]==0)
                     j/=x[t];}
      if(j>1)
              h[i]=(h[i]/j)*(j-1);}
scanf("%ld",&n);
while(n--)
      {scanf("%ld",&m);
      y=2*m*h[m],i=0;
      while(y)
            v[++i]=y%10+48,y/=10;
      for(j=i;j;j--)
            z[i-j+1]=v[j];
      puts(z);}
return 0;}