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)