#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

void _main() {
    vector<int> mul(100001, 1), cum(100001, 0);
    for (int i = 2; i <= 100000; ++i) {
        for (int j = 2 * i; j <= 100000; j += i) if (!cum[j]) {
            mul[j] *= i;
            if (mul[j] >= 2 * j) cum[j] = 1;
        }
    }
    for (int i = 2; i <= 100000; ++i) {
        cum[i] += cum[i - 1];
    }
    int Q;
    cin >> Q;
    REP (i, Q) {
        int N;
        cin >> N;
        cout << cum[N] << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    _main();
    return 0;
}
