d = {} for i in range(1, 10**5): if i * i > 10**9: break cnt = [0] * 10 s = str(i * i) for c in s: cnt[int(c)] += 1 if tuple(cnt) in d: continue d[tuple(cnt)] = i * i for _ in range(int(input())): N = int(input()) cnt = [0] * 10 ans = float("inf") for c in str(N): cnt[int(c)] += 1 t = cnt[0] for i in range(t + 1): cnt[0] = i if tuple(cnt) in d: ans = min(ans, d[tuple(cnt)]) if ans == float("inf"): ans = -1 print(ans)