#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#include <cstring>
#define MX 10000000
using namespace std;
int a[MX];
int N;
bool hasSeven(int n) {
    while (n > 0) {
        if( (n % 10) == 7) {
            return true;
        }
        n /= 10;
    }
    return false;
}
int main() {
    cin >> N;
    for (int i=7; i < MX;i++) {
        if (a[i] > 0) continue;
        if (hasSeven(i)) {
            for (int j=1; j<MX/i; j++) {
                    a[j*i] = 1;
            }
        }
    }
    for (int i=0; i<N; i++) {
        int k;
        cin >> k;
        if (a[k] == 1)
            cout << -1 << endl;
        else {
            for (int m=k+1; m < MX; m++) {
                if (a[m] == 0) {
                    cout << m << endl;
                    break;
                }
            }
        }
    }
 
    return 0;
}