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