#include <bits/stdc++.h>
using ll = long long;
using namespace std;

constexpr int M = 1e7;
ll a[M + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

    for (int i = 2; i <= M; i++) {
        a[i] = i;
    }
    for (int i = 2; i <= M; i++) {
        if (i == a[i]) {
            for (int j = i; j <= M; j += i) {
                a[j] = (int)a[j] / i * (i - 1);
            }
        }
        a[i] = a[i - 1] + (i - 1) * 2 - a[i];
    }

    while (t--) {
        int n;
        cin >> n;

        cout << a[n] << '\n';
    }

    return 0;
}