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

const int N=1e7+100;

ll sum_u[N];
ll sum_phi[N];
int u[5005001];
ll phi[5005001];
int cnt;
int p[5005001];
int vis[5005001];
int up;

ll get_sumu(int x) {
	if(x<=up) return sum_u[x];
	if(x<=10000000&&sum_u[x]) return sum_u[x];
	ll res=1ll;
	
	for(int l=2,r; l<=x; l=r+1) {
		r=x/(x/l);
		res-= (r-l+1)*get_sumu(x/l);
	}
	if(x<=10000000) sum_u[x]=res;
	return res;
}

ll get_phi(int x) {
	if(x<=up) return sum_phi[x];
	if(x<=10000000&&sum_phi[x]) return sum_phi[x];
	ll res=(x)*(x-1)/2;
	
	for(int l=2,r; l<=x; l=r+1) {
		r=x/(x/l);
		res-= (r-l+1) * get_phi(x/l);
	}
	if(x<=10000000) sum_phi[x]=res;
	return res;
}

void init_u (int n) {
	memset(p,0,sizeof(p));
	memset(vis,0,sizeof(vis));
	cnt=0;
	up=5e6;
	u[1]=1;
	for(int i=2; i<=up; i++) {
		if(!vis[i]) {
			p[++cnt]=i;
			u[i]=-1;
		} 
		for(int j=1; j<=cnt&&i*p[j]<=up; j++) {
			vis[i*p[j]]=1;
			if(i%p[j]) u[i*p[j]]=-u[i];
			else {
				u[i*p[j]]=0;
				break;
			}
		}
	}
	for(int i=1; i<=up; i++) sum_u[i]=sum_u[i-1]+u[i];
}

void init_phi(int n) {
	memset(p,0,sizeof(p));
	memset(vis,0,sizeof(vis));
	cnt=0;
	up=5e6;
	phi[1]=1;
	for(int i=2; i<=up; i++) {
		if(!vis[i]) {
			p[++cnt]=i;
			phi[i]=i-1;
		} 
		for(int j=1; j<=cnt&&p[j]*i<=up; j++) {
			vis[i*p[j]]=1;
			if(i%p[j]) phi[i*p[j]]=phi[i]*phi[p[j]];
			else {
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
		}
	}
	for(int i=1; i<=up; i++) sum_phi[i]=sum_phi[i-1]+phi[i];
}

int t;

signed main() {
	cin>>t;
	init_u(2147483647);
	init_phi(2147483647);
	while(t--) {
		int n;
		cin>>n;
		cout<<get_phi(n)<<" "<<get_sumu(n)<<endl;
	}
    return 0;
}

实测当 $n<=10^7$ 的时候还是对的。当 $n$ 更大的时候，莫比乌斯函数并没有计算错误，但欧拉函数出现了较小的偏差。