#include<bits/stdc++.h>
using namespace std;
#define N int(5e6)+7
int8_t vis[N];int mob[N],pri[N],T,n,cnt;int64_t phi[N];
void sieve(){
	phi[1]=1;mob[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i])pri[cnt++]=i,mob[i]=-1,phi[i]=i-1;
		for(int j=0;j<cnt&&i*pri[j]<N;j++){
			vis[i*pri[j]]=1;
			if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}
			phi[i*pri[j]]=phi[i]*phi[pri[j]];
			mob[i*pri[j]]=-mob[i];
		}
	}for(int i=2;i<N;i++)mob[i]+=mob[i-1],phi[i]+=phi[i-1];
}int mob_sum(int x){
	if(x<N)return mob[x];
	int ans=1;
	for(int L=1,R;L<=x;L=R+1){
		R=x/(x/L);
		ans-=(R-L+1)*mob_sum(x/L);
	}return ans;
}int64_t phi_sum(int x){
	if(x<N)return phi[x];
	int64_t ans=x*(x+1)/2;
	for(int L=1,R;L<=x;L=R+1){
		R=x/(x/L);
		ans-=(R-L+1)*phi_sum(x/L);
	}return ans;
}signed main(){
	sieve();
	cin>>T;
	while(T--){
		cin>>n;
		cout<<phi_sum(n)<<' '<<mob_sum(n)<<'\n';
	}
}

提交记录