#include
using namespace std;
typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int)
struct node { int v; dint phi, mu; node *next; };
const int maxv = 3000009; const int hmod = 4432457;
int n, tp, pn[maxv], phi[maxv], mu[maxv]; dint sp[maxv], smu[maxv]; bool pr[maxv]; node *head[hmod];
void pre() { memset(pr, 0, sizeof(pr)); memset(head, 0, sizeof(head)); tp = 0; phi[1] = mu[1] = 1; for (int i = 2; i < maxv; ++ i) { if (!pr[i]) { pn[tp ++] = i; mu[i] = -1; phi[i] = i - 1; } for (int j = 0, v; j < tp && i * pn[j] < maxv; ++ j) { pr[v = i * pn[j]] = 1; if (i % pn[j]) { mu[v] = - mu[i]; phi[v] = phi[i] * (pn[j] - 1); } else { mu[v] = 0; phi[v] = phi[i] * pn[j]; break; } } } smu[0] = sp[0] = 0; for (int i = 1; i < maxv; ++ i) { smu[i] = smu[i - 1] + mu[i]; sp[i] = sp[i - 1] + phi[i]; } }
void getVal(int x, dint& u, dint& p) { if (x < maxv) { u = smu[x]; p = sp[x]; } else { node* it; for (it = head[x % hmod]; it; it = it-> next) if (it-> v == x) { u = it-> mu; p = it-> phi; break; } if (!it) { u = 1, p = _l x * (_l x + 1) / 2; for (dint i = 2, j; i <= x; i = j + 1) { j = x / (x / i); dint ux, px; getVal(x / i, ux, px); u -= ux * (j - i + 1); p -= px * (j - i + 1); } it = new node; it-> v = x; it-> mu = u; it-> phi = p; it-> next = head[x % hmod]; head[x % hmod] = it; } } }
void sov() { dint uo, po; getVal(n, uo, po); printf(lld " " lld “\n”, po, uo); }
int main() { #ifndef ONLINE_JUDGE freopen(".in", “r”, stdin); #endif
pre();
int t;
scanf("%d", &t);
while (t --) {
scanf("%d", &n);
sov();
}
}