#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<int> prime;
vector<char> mark;
void sieve()
{
    mark.assign(257,0);
    for (int i = 2; i <= 256; i++)
    {
        if(mark[i] == 0)
        {
            prime.push_back(i);
            for (int j = i * i; j <= 256; j += i)
            {
                mark[j] = 1;
            }
        }
    }
}
long long binpow(long long a,long long n,long long m)
{
    long long r = 1;
    while(n)
    {
        if(n & 1){  r *= a; r %= m; }
        a *= a;
        a %= m;
        n >>= 1;
    }
    return r;
}
int di[50] = {0};
int fact(int p)
{
    int cnt = 0;
    for (int i = 0; i < prime.size(); i++)
    {
        if(prime[i] >= p)
            break;
        if(p % prime[i] == 0)
        {
            di[cnt] = prime[i];
            cnt++;
            while(p % prime[i] == 0)
            {
                p /= prime[i];
            }
        }
    }
    if(p > 1)
    {
        di[cnt] = p;
        cnt++;
    }
    return cnt;
}
int main()
{
    //freopen ("input.txt","r",stdin);
    sieve();
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        int n;
        scanf ("%d",&n);
        int mx = -1;
        int id = -1;
        int phi = n - 1;
        int cnt = fact(phi);
        for (int res = n - 1; res >= 2; --res)
        {
            bool ok = true;
            for (int i = 0; i < cnt && ok; ++i)
                ok &= binpow(res,phi / di[i],n) != 1;
            if(ok)
            {
                id = res;
                break;
            }
        }
        printf ("%d\n",id);
    }
    return 0;
}