#include<bits/stdc++.h>
using namespace std;
int m[10005],a[10005],i111=0;int n;
void l(int o){
	int u=o;
	for(int i=2;i<o-1;i++){
		
		if(u%i==0){
			m[i111]++;
			
			if(m[i111]>2){
				printf("0\n");
				return;
			}
			
			while(u%i==0){
				u/=i;
				
			}
			
		}
	}
	
	if(m[i111]==2){
		printf("1\n");
		return;
	}
	else{
		printf("0\n");
		return;
	}
}
int main(){
	
	scanf("%d",&n);
	for(;i111<n;i111++){
		scanf("%d",&a[i111]);
		l(a[i111]);
	}
}

TLE咋办？