#include using namespace std; int64_t power(int64_t n, int64_t k, int64_t mod) { if (k == 0) return 1; int64_t res = power(n * n % mod, k / 2, mod); if (k % 2) { res = res * n % mod; } return res; } int solve(int n) { int64_t mod = 2 * n - 1; map v; int64_t x = 1; for (int i = 1; i <= 50000; i++) { x = 2 * x % mod; if (x == 1) return i; v[x] = i; } int64_t m = power(x, mod - 2, mod), y = 1; for (int i = 1; i <= 50000; i++) { y = y * m % mod; if (v[y]) { return 50000 * i + v[y]; } } return -1; } int main() { int t; cin >> t; for (int i = 0; i < t; i++) { int n; cin >> n; cout << solve(n) << endl; } }