N = int(input())
P = [int(input()) for i in range(N)]

for p in P:
    a = 2
    for i in range(1,p*2):
        if i%p==a:
            print(i)
            break
        a *= 2
        a %= p