#include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 1e6+7;
const int MOD = 1e9+7;

#define DEBUG true
#define DATA 1
#define STD 2
#define VALID 3

int random(int x){
    return (LL)rand()%rand()%x;
}


void stdinout(int k, int status){
    string file_in  = "testcase/" + to_string(k) + ".in";
    string file_out = "testcase/" + to_string(k) + ".out";
    if(1==status){
        freopen(file_in.c_str(), "w" ,stdout);
    }
    else if(2==status){
        freopen(file_in.c_str(), "r", stdin);
        freopen(file_out.c_str(), "w", stdout);
    }
    else if(3==status){
        freopen(file_in.c_str(), "r", stdin);
    }
}

#define sfi(a) scanf("%d",&a)
#define sfd(a) scanf("%lf",&a)
#define sfl(a) scanf("%lld",&a)
#define sfs(a) scanf("%s",a)
 
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define dwn(i,b,a) for(int i=int(b-1);i>=int(a);--i)
 
#define mem(a,p) memset(a,p,sizeof(a))
 
#pragma comment(linker,"/STACK:102400000,102400000")
 

typedef unsigned UINT;
typedef unsigned long long ULL;
 
const int MAXN=100000;
 
bool vis[MAXN+5];
int prime[MAXN+5],cnt;
int phi[MAXN+5];
int mi[MAXN+5];
int muda[MAXN+5];
 
void init()
{
    memset(vis,0,sizeof(vis));
    phi[1]=1;
    mi[1]=1;
    cnt=0;
    for(int i=2;i<=MAXN;i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
            phi[i]=i-1;
            mi[i]=-1;
        }
        for(int j=0;j<cnt&&i*prime[j]<=MAXN;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j])
            {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
                mi[i*prime[j]]=-mi[i];
            }
            else
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                mi[i*prime[j]]=0;
                break;
            }
        }
    }

    memset(muda,0,sizeof(muda));
    for(int i=1;i<=MAXN;i++)
    {
        for(int j=1;j*i<=MAXN;j++)
            muda[j*i]+=i*mi[i];
    }
}
 
 
int run()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d\n",&n);
        printf("%d\n",muda[n]);
    }
    return 0;
}

void work(){
    for(int i=1;i<=10;i++){
        stdinout(i, STD);
        run();
    }
}

int main(){
    srand((unsigned)time(NULL));
    run();
    return 0;
}