#include<iostream>
#include<math.h>
using namespace std;
int tim1(int n)
{
	if(n<2)
	return 0;
	if(n==2||n==3)
	return 1;
	if(n%2==0||n%3==0)
	return 0;
	for(int i=5;i<=sqrt(n);i=i+6)
	if(n%i==0||(n+2)%i==0)
	return 0;
	return 1;
	
}
int tim(int n)
{
	int d=0,i;
	for(i=2;i<=n;i++)
	{
		if(tim1(i)==1)
		d=d+1;
}
	return d;
}
int main()
{
	int a[100000],i,n;
	cin>>n;
	for(i=1;i<=n;i++)
	cin>>a[i];
	for(i=1;i<=n;i++)
	{
	tim(a[i]);
	cout<<tim(a[i])<<endl;
     }
}