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

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

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

$$(n-1)!  \equiv -1\ (\bmod\ n)$$

$$(n-1)!  \equiv n-1\ (\bmod\ n)$$

$$(n-2)!  \equiv 1\ (\bmod\ n)$$

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

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

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

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