d={}
for i in range(1,100000):
  s=str(i**2)
  c=[0]*10
  for v in s:
    c[int(v)]+=1
  c=tuple(c)
  if c not in d:
    d[c]=i**2
T=int(input())
for _ in range(T):
  n=input()
  c=[0]*10
  for v in n:
    c[int(v)]+=1
  X=10**10
  ans=X
  while c[0]>=0:
    if tuple(c) in d:
      ans=min(ans,d[tuple(c)])
    c[0]-=1
  print(ans if ans<X else -1)