首先特判 $n \le 2$ 的情况。

很明显，当 $x \ge n$ 时，$n\mid x!$，因此答案不可能大于 $n-1$。

当 $n$ 为质数时，由威尔逊定理可得：

因此答案一定是 $n-2$。

当 $n$ 为合数时，由题意可知 $p\nmid x!$，其中 $p$ 是 $n$ 的最小素因子。

显然 $p \le \sqrt{n}$，并且答案不大于 $p-1$，暴力枚举即可。

最终的时间复杂度是 $O(T\sqrt{n})$。

#include <bits/stdc++.h>
using namespace std;
bool prime(int n)
{
	if (n == 1) return false;
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0) return false;
	return true;
}
int solve(int n)
{
	if (n <= 2) return n - 1;
	if (prime(n)) return n - 2;
	long long f = 1;
	int ans = 1;
	for (int i = 2; n % i != 0; i++)
	{
		f = f * i % n;
		if (f == 1) ans = i;
	}
	return ans;
}
int main()
{
	freopen("factorial.in", "r", stdin);
	freopen("factorial.out", "w", stdout);
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		cout << solve(n) << endl;
	}
	return 0;
}