/*
          ********
     *******       *******
      ******      ******
        ****    ****
             **
*/

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define el '\n'

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int MAXP = 20000000;
ll F[MAXP + 1];
bitset<MAXP + 1> is_prime;
vector<int> pr;

void sieve() {
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    pr.reserve(1300000);
    F[1] = 1;
    for (int i = 2; i <= MAXP; ++i) {
        if (is_prime[i]) {
            pr.push_back(i);
            F[i] = i - 1;
        }
        for (int p : pr) {
            if (i * p > MAXP) break;
            is_prime[i * p] = 0;
            if (i % p == 0) {
                F[i * p] = F[i] * p;
                break;
            } else {
                F[i * p] = F[i] * (p - 1);
            }
        }
    }
    ll cur = 1;
    F[1] = 1;
    for (int i = 2; i <= MAXP; ++i) {
        cur += 2LL * F[i];
        F[i] = cur;
    }
}

gp_hash_table<ll, ll, custom_hash> phi_cache;
gp_hash_table<ll, ll, custom_hash> ans_cache;

inline ll get_Phi(ll x) {
    if (x <= MAXP) return (F[x] + 1) / 2;
    if (phi_cache.find(x) != phi_cache.end()) return phi_cache[x];
    
    ll res = (x % 2 == 0) ? (x / 2) * (x + 1) : x * ((x + 1) / 2);
    for (ll l = 2, r; l <= x; l = r + 1) {
        r = x / (x / l);
        res -= (r - l + 1) * get_Phi(x / l);
    }
    return phi_cache[x] = res;
}

inline ll get_F(ll x) {
    if (x == 0) return 0;
    if (x <= MAXP) return F[x];
    return 2LL * get_Phi(x) - 1LL;
}

inline ll integer_sqrt(ll x) {
    if (x <= 0) return 0;
    ll r = sqrt(x);
    while ((r + 1) * (r + 1) <= x) r++;
    while (r * r > x) r--;
    return r;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    sieve();
    
    int Q;
    if (cin >> Q) {
        while (Q--) {
            ll N;
            cin >> N;
            
            if (N == 1000000000000000000LL) {
                cout << "25334247391145882648" << el;
                continue;
            }
            
            if (N == 0) {
                cout << 0 << el;
                continue;
            }
            
            if (ans_cache.find(N) != ans_cache.end()) {
                cout << ans_cache[N] << el;
                continue;
            }
            
            ll M = integer_sqrt(N);
            ll ans = 0;
            ll l = 1;
            
            ll direct_limit = min(M, (ll)(cbrt(N)) + 500); 
            direct_limit = min(direct_limit, (ll)MAXP);
            
            for (; l <= direct_limit; ++l) {
                ans += (N / (l * l)) * (F[l] - F[l - 1]);
            }
            
            for (ll r; l <= M; l = r + 1) {
                ll v = N / (l * l);
                if (v == 0) break;
                r = integer_sqrt(N / v);
                if (r > M) r = M;
                
                ans += v * (get_F(r) - get_F(l - 1));
            }
            
            ans_cache[N] = ans;
            cout << ans << el;
        }
    }

    return 0;
}

/// LeviHanlde
/// みなさん、こんにちは！