#include <bits/stdc++.h>
using namespace std;

const int N = 10000006;
bool f[N];  
int T, x;

inline bool c7(int x) { 
    while (x) {
        if (x % 10 == 7) return true;
        x /= 10;
    }
    return false;
}

void p() {
    for (int i = 1; i < N; ++i) {
        if (i % 7 == 0 || c7(i)) {
            for (int j = i; j < N; j += i) {
                f[j] = true;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    p();  
    
    cin >> T;
    while (T--) {
        cin >> x;
        if (f[x]) {
            cout << -1<<"\n";
        } else {
            int y = x + 1;
            while (y < N && f[y]) {
                ++y;
            }
           if(y<N)cout<<y<<"\n";
           else cout<<-1<<"\n";
        }
    }
    return 0;
}