#include <algorithm> #include <cstdio> using namespace std; using i64 = long long; using i128 = __int128_t; i64 phi(i64 n) { i64 res = n; for (i64 i = 2; i * i <= n; ++i) { if (n % i == 0) { res /= i; res *= i - 1; } while (n % i == 0) n /= i; } if (n > 1) { res /= n; res *= n - 1; } return res; } i64 power(i64 x, i64 y, i64 mod) { i64 res = 1; for (; y > 0; y >>= 1, x = (i128)(x % mod) * (x % mod) % mod) { if (y & 1) res = res * (i128)(x % mod) % mod; } return res; } void solve_test() { i64 n; scanf("%lld", &n); i64 m = (n << 1) - 1, phi_m = phi(m), ans = phi_m; for (i64 i = 1; i * i <= phi_m; ++i) { if (phi_m % i != 0) continue; if (power(2, i, m) == 1) ans = min(ans, i); if (i * i != phi_m && power(2, phi_m / i, m) == 1) ans = min(ans, phi_m / i); } printf("%lld\n", ans); } int main() { int t; scanf("%d", &t); while (t-- > 0) solve_test(); return 0; }