N, *p = map(int, open(0).read().split())

for e in p:
    t = 1
    x = 0
    for x in range(10000):
        t *= 2
        t %= e
        x += 1
        if t == x % e:
            print(x)
            break
    else:
        print(-1)