/*input
1
10
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e6 + 100;
#define int long long
#define pii pair<int, int>
#define f first
#define s second
inline pii mp(int a, int b)
{
pii temp;temp.f=a;temp.s=b;return temp;
}
vector<bool> isp(N, 1);int pref[N];
signed main()
{
//freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
isp[1]=0;
for(int i=2;i<N;i++)
{
if(isp[i])
{
for(int j=i*i;j<N;j+=i) isp[j]=0;
}
}
pref[1]=0;
for(int i=2;i<N;i++){
pref[i]=pref[i-1];
if(isp[i]) pref[i]++;
}
int q;cin>>q;
while(q--)
{
int n;cin>>n;
cout<<pref[n]<<endl;
}
}
LyppbnB1dAoxCjEwCiovCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBOPTFlNiArIDEwMDsKI2RlZmluZSBpbnQgbG9uZyBsb25nCiNkZWZpbmUgcGlpIHBhaXI8aW50LCBpbnQ+CiNkZWZpbmUgZiBmaXJzdAojZGVmaW5lIHMgc2Vjb25kCmlubGluZSBwaWkgbXAoaW50IGEsIGludCBiKQp7CglwaWkgdGVtcDt0ZW1wLmY9YTt0ZW1wLnM9YjtyZXR1cm4gdGVtcDsKfQp2ZWN0b3I8Ym9vbD4gaXNwKE4sIDEpO2ludCBwcmVmW05dOwpzaWduZWQgbWFpbigpCnsKCS8vZnJlb3BlbigiaW5wdXQudHh0IiwgInIiLCBzdGRpbik7ZnJlb3Blbigib3V0cHV0LnR4dCIsICJ3Iiwgc3Rkb3V0KTsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpO2Npbi50aWUoTlVMTCk7Y291dC50aWUoTlVMTCk7Cglpc3BbMV09MDsKCWZvcihpbnQgaT0yO2k8TjtpKyspCgl7CgkJaWYoaXNwW2ldKQoJCXsKCQkJZm9yKGludCBqPWkqaTtqPE47ais9aSkgaXNwW2pdPTA7CgkJfQoJfQoJcHJlZlsxXT0wOwoJZm9yKGludCBpPTI7aTxOO2krKyl7CgkJcHJlZltpXT1wcmVmW2ktMV07CgkJaWYoaXNwW2ldKSBwcmVmW2ldKys7Cgl9CglpbnQgcTtjaW4+PnE7Cgl3aGlsZShxLS0pCgl7CgkJaW50IG47Y2luPj5uOwoJCWNvdXQ8PHByZWZbbl08PGVuZGw7Cgl9Cn0=