## https://yukicoder.me/problems/no/1232 import math def solve(p): if p == 2: return 2 sqrt_p = int(math.sqrt(p - 1)) divisors = [] for x in range(1, sqrt_p + 1): if (p - 1) % x == 0: q = (p - 1) // x divisors.append(x) if q != x: divisors.append(q) divisors.sort() min_d = -1 for d in divisors: if pow(2, d, p) == 1: min_d = d break ans = pow(min_d, p - 2, p) ans = ans * min_d return ans def main(): N = int(input()) answers = [] for _ in range(N): p = int(input()) ans = solve(p) answers.append(ans) for ans in answers: print(ans) if __name__ == "__main__": main()