#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;
}