#include <bits/stdc++.h>
using namespace std;
#define rep(i, d, u) for(int i = d; i <= u; ++i)
#define dep(i, u, d) for(int i = u; i >= d; --i)
#define cep(n) while(n--)
#define gep(i, a) for(int i = firs[a]; i; i = neig[i])
int ured() {
	int re = 0;
	char ch;
	do {
		ch = getchar();
	} while('9' < ch || ch < '0');
	do {
		re = re * 10 + (ch ^ '0');
	} while('0' <= (ch = getchar()) && ch <= '9');
	return re;
}
int ired() {
	int re = 0;
	char ch;
	bool st = 0;
	do {
		ch = getchar();
	} while(('9' < ch || ch < '0') && ch != '-');
	if(ch == '-') {
		ch = getchar(), st = 1;
	}
	do {
		re = re * 10 + (ch ^ '0');
	} while('0' <= (ch = getchar()) && ch <= '9');
	return st ? -re : re;
}
void uwit(int da) {
	int ch[21], cn = 0;
	do {
		ch[++cn] = da - da / 10 * 10;
	} while(da /= 10);
	do {
		putchar('0' ^ ch[cn]);
	} while(--cn);
}
const int _maxn = 30000011, _maxa = 30000000;
struct node {
	int le, ri;
} arry[_maxn * 2];
bool operator<(node le, node ri) {
	return le . ri - le . le > ri . ri - ri . le;
}
priority_queue<node> queu;
int t, x[_maxn], mina[_maxn], prim[_maxn], coun, cnts, atpo, sran[_maxn], rans[_maxn];
bool visi[_maxn], pdif;
int main() {
	t = ured();
	rep(i, 1, t) {
		x[sran[i] = i] = ired();
	}
	rep(i, 2, _maxa) {
		if(!mina[i]) {
			mina[i] = prim[++coun] = i, visi[i] = 1;
		}
		for(int j = 1; j <= coun && i * prim[j] <= _maxa; ++j) {
			mina[i * prim[j]] = prim[j];
		}
	}
	rep(i, 1, _maxa) {
		if(visi[i]) {
			arry[++cnts] . le = i, arry[cnts] . ri = i, arry[++cnts] . le = -i + 1, arry[cnts] . ri = i;
		}
		if((i << 1 | 1) <= _maxa && visi[i << 1 | 1]) {
			arry[++cnts] . le = i, arry[cnts] . ri = i + 1, arry[++cnts] . le = -i + 1, arry[cnts] . ri = i + 1;
		}
	}
	sort(arry + 1, arry + cnts + 1, [](node le, node ri) {
		return le . le < ri . le;
	}), sort(sran + 1, sran + t + 1, [](int le, int ri) {
		return x[le] < x[ri];
	});
	rep(i, 1, t) {
		while(atpo + 1 <= cnts && arry[atpo + 1] . le <= x[sran[i]]) {
			queu . push(arry[++atpo]);
		}
		while(queu . top() . ri < x[sran[i]]) {
			queu . pop();
		}
		rans[sran[i]] = queu . top() . ri - queu . top() . le + 1;
	}
	rep(i, 1, t) {
		uwit(rans[i]), putchar('\n');
	}
	return 0;
}