如题，刚学杜教筛，很多细节都不知道怎么处理，希望巨佬多多指教 awa

//SIXIANG
#include <iostream>
#include <vector>
#define	MAXN 1000000
#define ll long long
using namespace std;
const int Mod = 1e6 + 3;
const int M = 1664510;

struct node {
	int id;
	ll val;
	node(int I, ll V) {
		id = I, val = V;
	}
};
vector <node> hasmu[Mod + 10], hasph[Mod + 10];
void Insertmu(int id, ll val) {hasmu[id % Mod].push_back(node(id, val));}
ll Findmu(int id) {
	for(int p = 0; p < hasmu[id % Mod].size(); p++)
		if(hasmu[id % Mod][p].id == id)
			return hasmu[id % Mod][p].val;
	return -1;
}
void Insertph(int id, ll val) {hasph[id % Mod].push_back(node(id, val));}
ll Findph(int id) {
	for(int p = 0; p < hasph[id % Mod].size(); p++)
		if(hasph[id % Mod][p].id == id)
			return hasph[id % Mod][p].val;
	return -1;
}

ll summu[M + 10], sumph[M + 10];
int pri[M + 10], ph[M + 10], mu[M + 10], tot = 0;
bool flag[M + 10];
void prepare() {
	mu[1] = ph[1] = 1;
	flag[1] = 1;
	for(int p = 2; p <= M; p++) {
		if(!flag[p]) pri[++tot] = p, mu[p] = -1, ph[p] = p - 1;
		for(int i = 1; i <= tot && pri[i] * p <= M; i++) {
			flag[pri[i] * p] = 1;
			if(p % pri[i] == 0) {
				mu[pri[i] * p] = 0;
				ph[pri[i] * p] = ph[p] * pri[i]; 
			}
			else {
				mu[pri[i] * p] = mu[pri[i]] * mu[p];
				ph[pri[i] * p] = ph[pri[i]] * ph[p];
			}
		}
	}
	for(int p = 1; p <= M; p++) {
		summu[p] = summu[p - 1] + 1ll * mu[p];
		sumph[p] = sumph[p - 1] + 1ll * ph[p];
	}
}

ll getSmu(int n) {
	if(n <= M) return summu[n];
	ll ans = 1;
	ll val = Findmu(n);
	if(val != -1) return val; 
	for(int l = 2, r; l <= n; l = r + 1) {
		r = min(n, n / (n / l));
		ans -= (r - l + 1) * getSmu(n / l);
	}
	Insertmu(n, val);
	return ans;
}
ll getSph(int n) {
	if(n <= M) return sumph[n];
	ll ans = 1ll * n * (n + 1) / 2;
	ll val = Findph(n);
	if(val != -1) return val; 
	for(int l = 2, r; l <= n; l = r + 1) {
		r = min(n, n / (n / l));
		ans -= (r - l + 1) * getSph(n / l);
	}
	Insertph(n, val);
	return ans;
}
signed main() {
	prepare();
	int T; cin >> T;
	while(T--) {
		int n; cin >> n;
		cout << getSph(n) << ' ' << getSmu(n) << endl; 
	}
}