#include <bits/stdc++.h>
using namespace std;
const int N = 10000010;
bool pri[N];
int p[N], lp;

bool check(int x) {
	if(x < 2) return 0;
	if(x <= 10000000) return !pri[x];
	for(int i = 1; 1ll * p[i] * p[i] <= x; i++) {
		if(x % p[i] == 0) return 0;
	}
	return 1;
}
void solve() {
	int x; cin >> x;
	if(x == 0) {
		cout << 3 << "\n"; return ;
	}
	if(x == 1) {
		cout << 2 << "\n"; return ;
	}
	if(x > 0) {
		if(!pri[x]) {
			cout << 1 << "\n";
		}
		else if(check(x + x - 1) || check(x + x + 1)) {
			cout << 2 << "\n";
		}
		else cout << "-1\n";
		return ;
	}
	if(check(-x + 1)) {
		cout << -2 * x + 1 + 1 << "\n";
		return ;
	}
	if(check(-x + 2 - x + 1)) {
		cout << -2 * x + 1 + 2 << "\n";
		return ;
	}
	cout << "-1\n";
}
int main() {
	ios::sync_with_stdio(0); cin.tie(nullptr);
	pri[1] = pri[0] = 1;
	for(int i = 2; i <= 10000000; i++) {
		if(!pri[i]) p[++lp] = i;
		for(int j = 1; 1ll * p[j] * i <= 10000000; j++) {
			pri[p[j] * i] = 1;
			if(i % p[j] == 0) break;
		}
	}
	int T; cin >> T;
	for(; T; --T) solve();
	return 0;
}