T={}
for x in range(1,10**5):
    y=x**2
    h=[]
    z=str(y)
    for i in range(len(z)):
        h.append(z[i])
    h.sort()
    p=''.join(h)
    if not p in T:
        T[p]=y
Q=int(input())
for _ in range(Q):
    N=int(input())
    h=[]
    c=str(N)
    for i in range(len(c)):
        h.append(c[i])
    h.sort()
    result=10**10
    for i in range(len(h)):
        u=h[i:]
        u.sort()
        p=''.join(u)
        if p in T:
            result=min(result,T[p])
        if h[i]!='0':
            break
    if result>10**9+6:
        result=-1
    print(result)