# ZeroJudge - f586: 數字D×D
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=f586
###### tags: `ZeroJudge` `數學` `質數`

#include <iostream>
#include <cmath>
using namespace std;
#define SIZE 1000080

int primes[SIZE], primeAmount;
bool notPrime[SIZE] = { true, true };

void Initialize() {
	for (int i = 2; i < SIZE; ++i) {
		if (!notPrime[i])
			primes[primeAmount] = i, ++primeAmount;
		for (int j = 0; i * primes[j] < SIZE; ++j) {
			notPrime[i * primes[j]] = true;
			if (!(i % primes[j]))
				break;
		}
	}
}

int Factorization(int number) {
	bool haveSquare = false;
	int primeFactors = 0, counts, buffer = sqrt(number);
	for (int i = 0; primes[i] <= buffer; ++i)
		if (!(number % primes[i])) {
			counts = 0;
			do {
				++counts;
				number /= primes[i];
			} while (!(number % primes[i]));
			haveSquare |= (counts > 1);
			++primeFactors;
		}
	if (number != 1)
		++primeFactors;
	return (haveSquare ? 0 : (primeFactors & 1 ? -1 : 1));
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	int times, number;
	Initialize();
	cin >> times;
	while (times--) {
		cin >> number;
		cout << Factorization(number) << '\n';
	}
}