#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    ll p[N];
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }
    ll v = 2;
    ll t = pow(10, 18);
    for (int i = 0; i < N; i++) {
        v = 4;
        bool flag = true;
        for (int x = 2; x < 60; x++) {
            if (v > t) break;
            if ((v % p[i]) == (x % p[i])) {
                flag = false;
                cout << x << "\n";
                break;
            }
            v *= 2;
        }
        if (flag) {
            cout << "-1\n";
        }
    }
    return 0;
}