rt 记录https://www.luogu.com.cn/record/51968385

#include<bits/stdc++.h>
using namespace std;
#define N 6000000
long long t;
long long phi[N+1000000],mu[N+1000000];
long long p[N],cnt=0;
bool isp[N+1000000];
map<int,long long> mp_phi,mp_mu;
void yu()
{
  isp[1]=1;
  mu[1]=1;
  phi[1]=1;
  for(long long i=2;i<=N+2;i++)
  {
    if(isp[i]==0)
      p[++cnt]=i,mu[i]=-1,phi[i]=i-1;
    for(long long j=1;j<=cnt&&i*p[j]<=N+2;j++)
    {
      if(i%p[j]==0)
      {
        isp[p[j]*i]=1,phi[p[j]*i]=phi[i]*p[j];
        break;
      } 
      else 
        isp[p[j]*i]=1,phi[p[j]*i]=phi[i]*(p[j]-1),mu[p[j]*i]=-mu[i];
    }
  }
  for(long long i=1;i<=N+2;i++) phi[i]+=phi[i-1],mu[i]+=mu[i-1];
}
long long dfkuaid1(long long k)
{
  long long ans=((k+1)*k)/2;
  if(k<=N) return phi[k];
  if(mp_phi[k]) return mp_phi[k];
  for(long long l=2,r;l<=k;l=r+1)
  {
    r=(k/(k/l));
    ans-=dfkuaid1(k/l)*(r-l+1);
  }
  return mp_phi[k]=ans;
}
long long dfkuaid2(long long k)
{
  long long ans=1;
  if(k<=N) return mu[k];
  if(mp_phi[k]) return mp_mu[k];
  for(long long l=2,r;l<=k;l=r+1)
  {
    r=(k/(k/l));
    ans-=dfkuaid2(k/l)*(r-l+1);
  }
  return mp_mu[k]=ans;
}
int main()
{
  cin>>t;
  yu();
  for(long long i=1;i<=t;i++)
  {
    long long n;
    cin>>n;
    cout<<dfkuaid1(n)<<" "<<dfkuaid2(n)<<endl;
  }
  return 0;
}