#include<bits/stdc++.h>
using namespace std;
bool fen(int m){
	int sum = 0,cc = 0;
	for(int i = 2;i<=m;i++){
		while(m%i == 0){
			m/=2;
			cc = 1;
		}
		if(cc = 1) sum++;
		cc = 0;
		if(m<=0||sum>2) break;
	}
	if(sum == 2) return true;
	return false;
}
int main(){
	long long n;
	cin>>n;
	for(int i = 0;i<n;i++){
		int m;
		cin>>m;
		cout<<fen(m)<<endl;
	}
	return 0;
}