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

bool check(int x) {
	if(x < 2) return 0;
	if(x <= 10000100) 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 {
			int t1 = f[x], t2 = g[x];
			t1 = 2 * t1, t2 = 2 * t2 + 1;
			cout << min(t1, t2) << "\n";
		}
		return ;
	}
	int t1 = f[-x + 1], t2 = g[-x + 1];
	t1 = 2 * t1, t2 = 2 * t2 + 1;
	cout << min(t1, t2) << "\n";
}
int main() {
	ios::sync_with_stdio(0); cin.tie(nullptr);
	pri[1] = pri[0] = 1;
	for(int i = 2; i <= 10000100; i++) {
		if(!pri[i]) p[++lp] = i;
		for(int j = 1; 1ll * p[j] * i <= 10000100; j++) {
			pri[p[j] * i] = 1;
			if(i % p[j] == 0) break;
		}
	}
	for(int i = 1; i <= 10000100; i++) {
		f[i] = !pri[i];
		g[i] = check(i + i + 1);
	}
	for(int i = 10000100; i; i--) {
		if(!f[i]) f[i] = f[i + 1];
		else f[i] = i;
		if(!g[i]) g[i] = g[i + 1];
		else g[i] = i;
	}
	int T; cin >> T;
	for(; T; --T) solve();
	return 0;
}