#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e7;
unordered_map<int,int> smu,sphi;
bool flg[maxn+5];
int phi[maxn+5],mu[maxn+5],r,n,p[maxn+5],cnt,T;
inline void Prime(int n){
	flg[0]=flg[1]=1;
	phi[1]=mu[1]=1;
	for(int i=2;i<=n;++i){
		if(!flg[i]){
			p[++cnt]=i;
			phi[i]=i-1;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt&&p[j]<=n/i;++j){
			flg[i*p[j]]=1;
			if(i%p[j]==0){
				phi[p[j]*i]=phi[i]*p[j];
				break;
			}
			phi[i*p[j]]=phi[i]*phi[p[j]];
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=n;++i){
		phi[i]+=phi[i-1];
		mu[i]+=mu[i-1];
	}
}
int Smu(int n){
	if(n<=maxn)
		return mu[n];
	if(smu[n])
		return smu[n];
	int res=1;
	for(int l=2;l<=n;l=r+1){
		r=n/(n/l);
		res-=(r-l+1)*Smu(n/l);
	}
	return smu[n]=res;
}
int Sphi(int n){
	if(n<=maxn)
		return phi[n];
	if(sphi[n])
		return sphi[n];
	int res=n*(n+1)/2;
	for(int l=2;l<=n;l=r+1){
		r=n/(n/l);
		res-=(r-l+1)*Sphi(n/l);
	}
	return sphi[n]=res;
}
signed main(){
	Prime(maxn);
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);
		printf("%lld %lld\n",Sphi(n),Smu(n));
	}
	return 0;
}