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