def main(): import sys input = sys.stdin.read().split() N = int(input[0]) primes = list(map(int, input[1:N+1])) for p in primes: if p == 2: print(2) continue found = False # Check x from 1 to 100_000 max_check = 100000 for x in range(1, max_check + 1): if pow(2, x, p) == x % p: print(x) found = True break if not found: x = (p - 1) ** 2 print(x) if __name__ == "__main__": main()