from collections import defaultdict

ans = defaultdict(lambda:-1)
for i in range(4*10**4,0,-1):
    a = sorted(str(i*i))
    for zero in range(10):
        ans[tuple(["0"]*zero + a)] = i*i

T = int(input())
for _ in range(T):
    N = input()
    print(ans[tuple(sorted(N))])