t,*ns=map(int,open(0).read().split())
s={}
for i in range(10**5):
  t=''.join(sorted(str(i*i)))
  if t not in s:
    s[t]=i*i
for n in ns:
  sn=sorted(str(n))[::-1]
  ans=INF=1<<60
  while 1:
    t=''.join(sorted(sn))
    if t in s:
      ans=min(ans,s[t])
    if sn[-1]=='0':
      sn.pop()
    else:
      break
  print([-1,ans][ans<INF])