#include <bits/stdc++.h>
using namespace std;
int n,m[210000],ans=0,jl,zd=0,oo[210000],l[210000];
int ans1(int b){
	int uu=0;
	for(int y=1;y<=b;y=y+2)uu+=(oo[y]&&oo[b%y]);
	return uu;
}
bool zss(long long a){
	if(a==2) return 1;
	if(a==1||a==0)return 0;
	for(int i=2;i<=sqrt(a);i++)if(a%i==0)return 0;
	return 1;
}
int read(){
	char ch=getchar();
	long long s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
int main()
{
	n=read();
	jl=n;
	for(int i=1;i<=n;i++){
		m[i]=read();
		if(m[i]>zd)for(int y=zd+1;y<=m[i];y++)oo[y]=zss(y);
	    zd=max(zd,m[i]);
	}
	for(int i=1;i<=n;i++){
		if(l[m[i]]==0)l[m[i]]=ans1(m[i]);
		printf("%d\n",l[m[i]]);
	}
	
    return 0;
} 

求各位大佬帮忙看看。