因为此题解中写道：

由 $\gcd(1,2,...,17)=12252240>10^6$，可知答案不大于 $17$，暴力即可。

所以，我们直接按题意模拟即可。

AC code：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int n;
        cin >> n;
        int ans = 2;
        for (; __gcd(ans, n) > 1; ans++) {
            if (__gcd(ans, n) == 1) {
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}