Sieve

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define endl '\n'
#define N 10000110

using namespace std;

ll lp[N+1];
vector<ll> pr;

void sieve(){
    for (ll i=2; i<=N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back (i);
        }
        for (ll j=0; j<(ll)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];
    }
}

int higher(ll x){
    int lo = 0, hi = (int)pr.size(), res = -1;
    while(lo <= hi){
        int mid = lo + (hi - lo)/2;
        if(pr[mid] > x){
            res = mid;
            hi = mid-1;
        }else if(pr[mid] < x){
            lo = mid+1;
        }else{
            return mid;
        }
    }
    return res;
}

int lower(ll x){
    int lo = 0, hi = (int)pr.size(), res = -1;
    while(lo <= hi){
        int mid = lo + (hi - lo)/2;
        if(pr[mid] > x){
            hi = mid-1;
        }else if(pr[mid] < x){
            res = mid;
            lo = mid+1;
        }else{
            return mid;
        }
    }
    return res;
}


void solve(){
    ll n;
    cin>>n;
    if(n == 2){
        cout<<1<<endl;
        return;
    }

    ll num = n/2 + 1;
    int lo = lower(n);
    int hi = higher(num);
    if(hi == 0)
        hi++;

    ll res = lo - hi + 2;
    cout<<res<<endl;

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve();
    int t;
    cin>>t;
    while(t--)
        solve();
}