Day 1 / D

#include<bits/stdc++.h>
using namespace std;
#define ll long long


vector<ll> build;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  freopen("input.txt","r",stdin), freopen("output.txt", "w", stdout);
    int TC = 1;
    cin>>TC;
    vector<bool> is_prime(1e7+5, true);
    for (ll i = 2; i <= 1e7; i++) {
    if (is_prime[i] && (ll)i * i <= 1e7) {
        for (ll j = i * i; j <= 1e7; j += i)
            is_prime[j] = false;
        }
    }
    for(ll i=2; i<=1e7; i++){
        if(is_prime[i])
            build.push_back(i*i);
    }
    while(TC--){
        ll n; cin>>n;

    // cout<<upper_bound(build.begin(),build.end(), n) - build.begin()<<'\n';
    // or you can build it by yourself

    int l = 0, r = build.size() - 1, best = -1;
    while(l <= r){
      ll mid = l + (r - l ) / 2;
      (build[mid] <= n ? l = mid + 1, best = mid : r = mid - 1);
    }
    cout<<best + 1<<'\n';
    }
}