#include <bits/stdc++.h>
using namespace std;
long long n,x,f;
bool a,b,s;
int main(){
	cin>>n;
	while(n--){
		cin>>x;
		f=x;
		a=b=s=true;
		for(long long i=2;i*i<=x;i++){
			if(f%i==0)while(f%i==0)f/=i;
			if(a)a=false;
			else if(b)b=false;
			else{
				cout<<0<<endl;
				s=false;
				f=1;
			}
			if(f==1)break;
		}
		if(s){
			if(f!=1&&!b)cout<<0<<endl;
			else if(!a&&!b)cout<<1<<endl;
			else cout<<0<<endl;
		}
	}
	return 0;
}