//完整缺省源请见洛谷云剪贴板 jo5j6ogx
const int N=2e6;
map<ll,ll>mp;
int t,prime[N+10],mu[N+10],ps;
bool b[N+10];
ll n,sum[N+10];
il void init(){
	b[0]=b[1]=1;
	mu[1]=1;
	for(int i=2;i<=N;i++){
		if(!b[i]){
			prime[++ps]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=ps&&i*prime[j]<=N;j++){
			b[i*prime[j]]=1;
			if(i%prime[j]){
				mu[i*prime[j]]=-mu[i];
			}else{
				mu[i*prime[j]]=0;
				break;
			}
		}
	}
	for(int i=1;i<=N;i++){
		sum[i]=sum[i-1]+mu[i];
	}
}
il ll sum_mu(ll n){
	if(n<=N){
		ret sum[n];
	}
	if(mp[n]){
		ret mp[n];
	}
	ll l=1,r,ans=1;
	while(l<=n){
		r=n/(n/l);
		ans-=(r-l+1)*sum_mu(n/l);
		l=r+1;
	}
	ret mp[n]=ans;
}
il ll sum_phi(ll n){
	ll l=1,r,ans=0;
	while(l<=n){
		r=n/(n/l);
		ans+=(n/l)*(n/l)*(sum_mu(r)-sum_mu(l-1));
		l=r+1;
	}
	ans=(ans-1)/2+1;
	ret ans;
}
int main(void){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	init();
	t=read<int>();
	while(t--){
		n=read<ll>();
		write(sum_phi(n));
		spe;
		write(sum_mu(n));
		edl;
	}
	ret 0;
}