#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cout << #x << ": " << x << '\n';

int solve(int n) {
    vector <int> a(2 * n);
    for (int i = 0; i < 2 * n; ++i)
        a[i] = i;

    auto was = a;

    auto f = [&] (vector <int> a) {
        vector <int> ans;
        for (int i = 0; i < n; ++i) {
            ans.app(a[i]);
            ans.app(a[i + n]);
        }   
        return ans;
    };  

    int ans = 0;
    while (1) {
        a = f(a);
        ans++;
        if (a == was) {
            return ans;
        }   
    }   
    assert(0);
}

int phi (int n) {
    int result = n;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    if (n > 1)
        result -= result / n;
    return result;
}

int fast_solve() {

}   

int fp(int a, int p, int mod) {
    int ans = 1, cur = a;
    for (int i = 0; (1ll << i) <= p; ++i) {
        if ((p >> i) & 1) {
            ans = (ans * cur) % mod;
        }   
        cur = (cur * cur) % mod;
    }   
    return ans;
}    

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(20); 
    #endif

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        if (n == 1) {
            cout << 1 << endl;
            continue;
        }   

        int mod = 2 * n - 1;
        int ph = phi(mod);
        vector <int> a;
        for (int d = 1; d * d <= ph; ++d) {
            if (ph % d == 0) {
                a.app(d);
                a.app(ph/d);
            }   
        }   
        sort(all(a));
        for (auto e : a) {
            if (fp(2, e, mod) == 1) {
                cout << e << endl;
                break;
            }   
        }   
    }

    exit(0);

    /*
    for (int n = 1; n <= 100; ++n) {
        //cout << n << ' ' << solve(n) << endl;
        cout << solve(n) << ' ';
    }   
    cout << endl;
    */


}