#include <stdio.h>

using namespace std;
int cmmdc(int a, int b)
{
    int c;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

unsigned long S,Nr,i,j,n;
int main()
{
    FILE*f=fopen("sum.in","r");
    FILE*g=fopen("sum.out","w");
    fscanf(f,"%lu",&n);
    for(i=1;i<=n;i++)
    {
        S=0;
        fscanf(f,"%lu",&Nr);
        for(j=1;j<2*Nr;j++)
            if(cmmdc(j,Nr)==1) S+=j;
        fprintf(g,"%lu\n",S);
    }



    fclose(f);
    fclose(g);
    return 0;
}