n = int(input())
for i in range(n):
    p = int(input())
    if p == 2:
        print(2)
        continue
    m = (p - 1)*pow(p-1,p-2,p)
    print(m)