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

for e in p:
    for x in range(1, min(10000, e)):
        if pow(2, x, e) == x % e:
            print(x)
            break
    else:
        print(-1)