import java.io.BufferedReader import java.io.InputStream import java.io.InputStreamReader import java.io.PrintWriter import java.util.* import java.math.BigInteger fun PrintWriter.solve(sc: FastScanner) { val t = sc.nextInt() for (_i in 0 until t) { val n = sc.nextLong() val m = 2 * n - 1 val phi = phi(m) var ans = Long.MAX_VALUE val number = phi val div = mutableListOf() var divisor = 1L while (divisor * divisor <= number) { if (number % divisor == 0L) { div.add(divisor) if (divisor * divisor != number) { div.add(number / divisor) } } divisor++ } for (d in div) { if (modpow(2, d, m) == 1L) { ans = minOf(ans, d) } } println(ans) } } fun phi(n: Long): Long { var res = n var i = 2L var m = n while (i * i <= m) { if (m % i == 0L) { res = res / i * (i - 1) while (m % i == 0L) { m /= i } } i++ } if (m > 1) { res = res / m * (m - 1) } return res } fun modpow(a: Long, n: Long, m: Long): Long { if (n == 0L) return 1 if (n == 1L) return a val pow = modpow(a, n / 2, m) var res = pow * pow % m if (n % 2 == 1L) { res *= a res %= m } return res } fun main() { val writer = PrintWriter(System.out, false) writer.solve(FastScanner(System.`in`)) writer.flush() } class FastScanner(s: InputStream) { private var st = StringTokenizer("") private val br = BufferedReader(InputStreamReader(s)) fun next(): String { while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine()) return st.nextToken() } fun nextInt() = next().toInt() fun nextLong() = next().toLong() fun nextLine() = br.readLine() fun nextDouble() = next().toDouble() fun ready() = br.ready() }