#include <fstream>
#define N 100010
#define LL long long

using namespace std;

FILE* fin=fopen("sum.in","r");
FILE* fout=fopen("sum.out","w");
const int maxb=8192;
char buf[maxb];
int ptr=0;

inline int getint() {
    int nr=0;
    while(buf[ptr]<'0'||'9'<buf[ptr])
        if (++ptr>=maxb) fread(buf,maxb,1,fin),ptr=0;
    while ('0'<=buf[ptr]&&buf[ptr]<='9') {
        nr=nr*10+buf[ptr]-'0';
        if (++ptr>=maxb) fread(buf,maxb,1,fin),ptr=0;
    }
    return nr;
}

LL A[N],x;
int i,j,t;

int main() {
    t=getint();
    for (i=1;i<=N-10;i++) A[i]=i-1;
    for (i=2;i<=N-10;A[i]*=2*i,i++)
        for (j=2*i;j<=N-10;j+=i)
            A[j]-=A[i];
    for (;t;--t) {
        x=getint();
        fprintf(fout,"%lld\n",A[x]);
    }
    fclose(fin);fclose(fout);
    return 0;
}