#include <bits/stdc++.h>
using namespace std;
int n,x;
const int N = 10000001;
bool a[N];
int num[N],cnt;
bool check(int n){
//	if(n % 7 == 0) return true;
	while(n){
		int m = n % 10;
		if(m == 7) return true;
		n /= 10;
	}
	return false;
}
int main(){
	cin >> n;
	for(register int i = 1; i < N; i++){
		if(a[i]) continue;
		if(check(i)){
			a[i] = true;
			for(int j = i; j < N; j += i){
				a[j] = true;
			}
			continue;
		}
		cnt++;
		num[cnt] = i;
	}
	for(register int i = 1; i <= n; i++){
		cin >> x;
		if(a[x]) cout << -1 << endl;
		else{
			int t = upper_bound(num + 1,num + 1 + cnt,x) - num;
			cout << num[t] << endl;
		} 
	}
	return 0;
}

献上CCCCCCCCCCCCCCCCORZ