#include<bits/stdc++.h>
using namespace std;

signed main(){
  cin.tie(0)->sync_with_stdio(0);
  map<vector<int>,int>mp;
  for(int i=1;i*i<=1'000'000'000;++i){
    vector<int>cnt(10);
    int n=i*i;
    while(n){
      ++cnt[n%10];
      n/=10;
    }
    if(mp.find(cnt)==mp.end()){
      mp[cnt]=i*i;
    }
  }
  int t;cin>>t;
  while(t--){
    int N;cin>>N;
    int ans=1<<30;
    vector<int>cnt(10);
    while(N){
      ++cnt[N%10];
      N/=10;
    }
    for(;0<=cnt[0];--cnt[0]){
      int v=mp[cnt];
      if(v)ans=min(ans,v);
    }
    if(ans==1<<30)ans=-1;
    cout<<ans<<'\n';
  }
}