N = int(input())

for _ in range(N):
    p = int(input())
    x = 1
    for i in range(10000):
        x *= 2
        x += i
        x %= p
        if x == 0:
            print(i+2)
            break
    else:
        print(-1)