#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int isPrime(int n){
	int flag=1;
	int limit=sqrt(1.0*n)+1;
	if(n%2==0)
		flag=0;
	else{
		for(int i=3;i<limit;i+=2){
			if(n%i==0){
				flag=0;
				break;
			}
		}
	}
	return flag;
}
int main(){
	int T;
	scanf("%d",&T);
	int m=0,dt=0;
	int ans=0;
	int flag=1;
	while(T--){
		int n;
		scanf("%d",&n);
		if(m<n){
			for(int i=m+1;i<=n;i++){
				if(isPrime(i)==1)
					ans++;
			}
		}
		else if(flag==1){
			flag=0;
			ans=1;
			for(int i=3;i<=n;i++){
				if(isPrime(i)==1)
					ans++;
			}
		}
		else{
			for(int i=n+1;i<=m;i++){
				if(isPrime(i)==1)
					ans--;
			}
		}
		printf("%d\n",ans);
		m=n;
		dt=ans;
	}                                                       
	return 0;
}