#include <stdio.h>
#include <stdlib.h>

int main()
{   FILE*fi,*fout;
    int s,j,j1,i,nr,nr1,n,r;
    fi=fopen("sum.in" ,"r");
    fout=fopen("sum.out" ,"w");
    fscanf(fi,"%d\n" ,&n);
    for(i=0;i<n;i++)
    {
        fscanf(fi,"%d\n" ,&nr);
        s=1;
        for(j=2;j<2*nr;j++)
        {
            j1=j;
            nr1=nr;
            if(j1!=nr1)
            {
               while(nr1>0)
               {
                   r=j1%nr1;
                   j1=nr1;
                   nr1=r;
               }
               if(j1==1)
                s=s+j;
            }
        }
       fprintf(fout,"%d\n" ,s);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}