def change_base(n, b):
    rem = ''
    while n > 0:
        rem += str((n % b))
        n /= b
    return rem[::-1]    

def pal_base(n):
    base = 2
    while 1:
        num = change_base(n, base)
        if num == num[::-1]:
            return base
        base += 1

t = int(raw_input())
i = 0
N = []
while i < t:
    N.append(int(raw_input()))
    i += 1
for i in N:
    print pal_base(i)