#include<stdio.h>
#include<math.h>
#define kk 1000001
int main ()
{
int t=0,n=0;//t个数输入n
int i=0,j=0,k=0;//循环
int cnt=0;//标记
int count=0;//计素数
int a[kk]={0};
for(j=2;j<=kk;j++)//数组顺存素数个数
{
cnt=0;//更新标记
for(k=2;k<=sqrt(j);k++)//开平方减少重复运算
{
if(j%k==0)//不是素数
{
cnt=1;
break;
}
}
if(cnt==0)//是素数
{
count++;
}
a[j]=count;//n前素数个数存入数组
}
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%d",&n);
printf("%d\n",a[n]);
}
return 0;
}