from collections import defaultdict

INF = int(1e9) + 2525
d = defaultdict(lambda: INF)

# count of digit 0-9
def get_frequency(value):
    c = [0] * 10
    while value != 0:
        c[value % 10] += 1
        value //= 10
    return c

x = 1
while x * x <= 10 ** 9:
    c = tuple(get_frequency(x * x))
    d[c] = min(d[c], x * x)
    x += 1

T = int(input())
for _ in range(T):
    N = int(input())
    c = get_frequency(N)
    ans = INF
    for i in range(c[0] + 1):
        ans = min(ans, d[tuple(c)])
        c[0] -= 1
    print(-1 if ans == INF else ans)