import sys import math def input(): return sys.stdin.read() def baby_step_giant_step(a, b, mod): if b == 1: return 0 m = int(math.isqrt(mod)) + 1 table = {} current = 1 for j in range(m): if current not in table: table[current] = j current = (current * a) % mod am_inv = pow(a, mod - m - 1, mod) gamma = b for i in range(m): if gamma in table: return i * m + table[gamma] gamma = (gamma * am_inv) % mod return -1 def crt(a1, m1, a2, m2): d = math.gcd(m1, m2) if (a1 - a2) % d != 0: return -1 lcm = m1 // d * m2 m1_dash = m1 // d m2_dash = m2 // d inv = pow(m1_dash, -1, m2_dash) k = (a2 - a1) // d % m2_dash x = (a1 + k * m1) % lcm return x def solve(): data = input().split() n = int(data[0]) primes = list(map(int, data[1:n+1])) for p in primes: if p == 2: print(2) continue found = False max_a = min(p-1, 1000) for a in range(max_a + 1): if pow(2, a, p) == a % p: b = baby_step_giant_step(2, a % p, p) if b == -1: continue x = crt(a, p, b, p-1) if x == -1: continue if x <= 0: x += p * (p-1) if x > 1e18: continue print(x) found = True break if not found: x = (p-1) ** 2 print(x) solve()