#include<bits/stdc++.h>
using namespace std;
using ll = long long;
bool f[100005];
void mkk() {
    fill(f + 2, f + 100005, true);
    for (int i = 2; i * i <= 100000; i++) {
        if (f[i]) {
            for (int j = i * i; j <= 100000; j += i) f[j] = false;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    mkk();
    int t;
    cin >> t;
    while (t--) {
        int h;
        cin >> h;
        int ans = 1e9;
        for (int k = 0; k <= 17; k++) {
            int p2 = 1 << k;
            if (h + 1 == p2) {
                ans = min(ans, k);
            }
            int x = h + 1 - p2;
            if (x >= 2 && x <= h && f[x]) {
                ans = min(ans, k + 1);
            }
        }
        if (ans > 1e8) cout << -1 << "\n";
        else cout << ans << "\n";
    }
    return 0;
}