n = int(input())
for i in range(n):
    p = int(input())
    if p == 2:
        print(2)
    else:
        print((p - 1) * (p - 1))
        t = (p - 1) * (p - 1)
        if pow(2, t, p) != t % p:
            print('WTF')