#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

int main() {

    long long T;
    long long big = 1000001;

    long long osztok[big];
    long long ertek[big];
    long long osszes[big];
    long long negyzet[big];

    for(long i = 0; i < big; i++) {
        osztok[i] = 0;
    }
    for(long i = 0; i < big; i++) {
        ertek[i] = 0;
    }
    for(long i = 0; i < big; i++) {
        osszes[i] = 0;
    }
    for(long i = 0; i < big; i++) {
        negyzet[i] = 0;
    }

    for(long i = 1; i < big; i++) {
        for(long j = i; j < big; j += i) {
            osztok[j]++;
        }
    }

    for(long i = 1; i < big; i++) {
        long k = 0;
        do {
            ertek[i*k] += osztok[k];
            k++;
        } while(i*k < big);
    }

    for(long i = 0; i < big; i++) {
        osztok[i] = 0;
    }


    for(long i = 1; i < sqrt(big); i++) {
        long mul = i*i;
        for(long j = mul; j < big; j += mul) {
            osztok[j]++;
        }
    }

    for(long i = 1; i < big; i++) {
        osszes[i] = ertek[i] + osszes[i-1];
    }

    for(long i = 1; i < big; i++) {
        negyzet[i] = osztok[i] + negyzet[i-1];
    }

    cin >> T;

    long long in;
    long long res = 0;

    while(T--) {
        cin >> in;
        long long cube = cbrt(in) / 1;
        //cout << "ossz: "<< osszes[in] << " negyzet: "<< negyzet[in] << endl;
        res = (osszes[in] + 2 * cube - negyzet[in]*3) / 6;
        cout << res << endl;
    }

    return 0;
}