#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define int long long
bool prime(int a) {
	if (a < 2) {
		return 0;
	} else if (a == 2) {
		return 1;
	} else if (a % 2 == 0) {
		return 0;
	}
	for (int i = 3; i <= sqrt(a); i++) {
		if (a % i == 0) {
			return 0;
		}
	}
	return 1;
}
vector<int> dnj(int n) {
	vector<int> f;
	if (n < 0) {
		f.push_back(-1);
		n = -n;
	}
	if (n == 0) {
		f.push_back(0);
		return f;
	}
	if (n == 1) {
		f.push_back(1);
		return f;
	}
	while (n % 2 == 0) {
		f.push_back(2);
		n /= 2;
	}
	for (int i = 3; i <= sqrt(n); i += 2) {
		while (n % i == 0) {
			f.push_back(i);
			n /= i;
		}
	}

	if (n > 2) {
		f.push_back(n);
	}

	return f;
}

signed main() {
	int n;
	cin >> n;
	int ans[n];
	int awa=0;
	while (n--) {
		int a;
		cin >> a;
		if (prime(a)) {
			ans[awa]=0;
		} else {
			int f[5];
			f[0]=0;
			f[1]=0;
			f[2]=0;
			f[3]=0;
			f[4]=0;
			int cnt = 1;
			f[0] = dnj(a)[0];
			for (int i = 1; i < dnj(a).size(); i++) {
				int c = 0;
				for (int j = 0; j < 5; j++) {
					if (dnj(a)[i] != f[j]) {
						c++;
					}
				}
				if (c == 5) {
					f[cnt] = dnj(a)[i];
					cnt++;
				}
			}
			if (cnt > 2) {
				ans[awa]=0;
			} else {
				ans[awa]=1;
			}
		}
		awa++;
	}
	for(int i=0;i<awa;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}