#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<unordered_map>

using namespace std;

const int N = 5e6;

unordered_map<int,long long>phi;

unordered_map<int,int>mu;

unordered_map<int,bool>visp,vism;

long long _p[N+];

int _m[N+];

int cnt,p[N];

bool is[N+];

inline long long get_phi(int x){

    if(x<=N)return _p[x];

    if(visp[x])return phi[x];

    long long res=(long long)x*(x+)/;

    int le=,ri;

    for(;le<=x;le=ri+){

      ri=x/(x/le);

      res-=(ri-le+)*get_phi(x/le);

    }

    visp[x]=;return phi[x]=res;

}

inline int get_mu(int x){

    if(x<=N)return _m[x];

    if(vism[x])return mu[x];

    int res=,le=,ri;

    for(;le<=x;le=ri+){

      ri=x/(x/le);

      res-=(ri-le+)*get_mu(x/le);

    }

    vism[x]=;return mu[x]=res;

}

inline void go(){

    register int i,j,k;

    _p[]=_m[]=;

    for(i=;i<=N;++i){

      if(!is[i])p[++cnt]=i,_m[i]=-,_p[i]=i-;

      for(j=;j<=cnt,i*p[j]<=N;++j){

          is[p[j]*i]=;

          if(i%p[j]==){

            _m[i*p[j]]=;

            _p[i*p[j]]=_p[i]*p[j];

            break;

          }

          _m[i*p[j]]=-_m[i];

          _p[i*p[j]]=_p[i]*(p[j]-);

      }

    }

    for(i=;i<=N;++i)_p[i]+=_p[i-],_m[i]+=_m[i-];

}

int main(){

    int n,t;

    scanf("%d",&t);

    go();

    while(t--){

      scanf("%d",&n);

      printf("%lld %d\n",get_phi(n),get_mu(n));

    }

    return ;

}