#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 5000007;
int prime[N];
bool vis[N];
int mu[N];
LL phi[N];
unordered_map<int, int> summu;
unordered_map<int, LL> sumphi;
void init()
{
    int cnt = 0;
    vis[0] = vis[1] = 1;
    mu[1] = phi[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!vis[i])
        {
            prime[cnt++] = i;
            mu[i] = -1;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && i * prime[j] < N; j++)
        {
            vis[i * prime[j]] = true;
            if (i % prime[j])
            {
                mu[i * prime[j]] = -mu[i];
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            }
            else
            {
                mu[i * prime[j]] = 0;
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
    for (int i = 1; i < N; i++)
    {
        mu[i] += mu[i - 1];
        phi[i] += phi[i - 1];
    }
}
LL getsmu(int x)
{
    if (x < N)
        return mu[x];
    if (summu[x])
        return summu[x];
    LL ans = 1;
    for (LL l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        ans -= 1ll * (r - l + 1) * getsmu(x / l);
    }
    return summu[x] = ans * 1ll;
}
LL getsphi(int x)
{
    if (x < N)
        return phi[x];
    if (sumphi[x])
        return sumphi[x];
    LL ans = x * ((LL)x + 1) / 2;
    for (LL l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        ans -= 1ll * (r - l + 1) * getsphi(x / l);
    }
    return sumphi[x] = ans * 1ll;
}
int main()
{
    init();
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        printf("%lld %lld\n", getsphi(n), getsmu(n));
    }
    return 0;
}