/* name: A
 * author: 5ab
 * created at: 2023-12-12
 */
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;
const int N = 2e7 + 114514;

bool isp[N + 1];
vector<int> prm;
int nxt[N + 1], nxt2[N + 1];

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int cas, x;
	
	isp[1] = 1;
	for (int i = 2; i <= N; i++)
	{
		if (!isp[i])
			prm.push_back(i);
		for (int j = 0; j < ssz(prm) && i * prm[j] <= N; j++)
		{
			isp[i * prm[j]] = 1;
			if (i % prm[j] == 0)
				break;
		}
	}
	nxt[N] = nxt2[N] = nxt2[N - 1] = -1;
	for (int i = N - 1; i > 0; i--)
	{
		if (!isp[i])
			nxt[i] = nxt2[i] = i;
		else
		{
			nxt[i] = nxt[i + 1];
			if (i + 2 <= N)
				nxt2[i] = nxt2[i + 2];
		}
	}
	
	cin >> cas;
	while (cas--)
	{
		cin >> x;
		
		int ans = 1145141919;
		if (x > 0 && !isp[x])
			chmin(ans, 1);
		if (x > 0 && (!isp[x + x + 1] || !isp[x + x - 1]))
			chmin(ans, 2);
		chmin(ans, nxt[abs(2 * x - 1) / 2 + 1] * 2);
		chmin(ans, nxt2[abs(x - 1) * 2 + 1]);
		
		cout << ans << "\n";
	}
	
	return 0;
}
// started coding at: 12-12 16:25:07