#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
bool prime[N];
int cntIdx=0;
int onlyPrime[N];
void sieve(){
	memset(prime,true,sizeof(prime));
	prime[1]=prime[0]=false;
	for(int i=2;i*i<=N-5;i++){
		if(prime[i]){
			for(int j=i*i;j<=N-5;j+=i){
				prime[j]=false;
			}
		}
	}
	for(int i=2;i<=N-5;i++){
		if(prime[i]){
			onlyPrime[cntIdx++]=i;
		}
	}
}
bool fac(int x){
	int i=0,sq=sqrt(x);
	int ans=1;
	while(onlyPrime[i]<=sq&&x>1){
		if(x%onlyPrime[i]==0){
			int cnt=1;
			while(x%onlyPrime[i]==0){
				++cnt;
				x/=onlyPrime[i];
			}
			ans*=(cnt+1);
		}
		++i;
	}
	if(x>1)ans*=2;
	return ans==2;
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	sieve();
	int t;
	cin>>t;
	while(t--) {
		int x;
		cin>>x;
		if(fac(x))cout<<1;
		else cout<<0;
		cout<<"\n";
	}
}