d = {}
for x in range(1, 31623):
    x2 = x * x
    st = ''.join(sorted(str(x2)))
    if st not in d:
        d[st] = x2
for _ in range(int(input())):
    st = ''.join(sorted(input()))
    ans = -1
    for i in range(len(st)):
        t = st[i:]
        if t in d:
            ans = d[t]
        if st[i] != '0':
            break
    print(ans)