T, = map(int, input().split())
for i in range(T):
    N, = map(int, input().split())
    c = 1
    i = 0
    while 1:
        i += 1
        c = c*2%(2*N-1)
        if c%(2*N-1) == 1:
            break
    print(i)