#include<iostream>
using namespace std;

long long N_MAX = 2000001;
bool isPrime[2000001];
long long cnt[2000001]; // cnt[i] la so cac so nguyen to tu 0 den i
void init();

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
   freopen ("input.txt", "r", stdin);
   freopen ("output.txt", "w", stdout);
#endif
    init();

    int n, t; cin >> n;

    for (long long i=0; i<n; i++){
        cin >> t;
        cout << cnt[2*t]-cnt[t] << endl;
    }

    return 0;
}


void init(){

    for (long long i=1; i<=N_MAX; i++){
        isPrime[i] = true;
        cnt[i] = 0;
    }

    // Sang nguyen to
    isPrime[0] = false;
    isPrime[1] = false;
    for (long long i=2; i<=N_MAX; ++i){
        if (isPrime[i]){
            cnt[i] = cnt[i-1]+1;
            for (long long j=i*i; j<=N_MAX; j+=i) isPrime[j] = false;
        }
        else cnt[i] = cnt[i-1];
    }
}