for _ in range(int(input())):
    p = int(input())
    if p==2:
        print(2)
    else:
        print(p**2-2*p+2)
        assert(pow(2,p**2-2*p+2,p)==(p**2-2*p+2)%p)