#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <chrono>
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define rep(i,n) for (ll i = 0;i < (ll)(n);i++)
#define Yes cout << "Yes" << "\n"// YESの短縮
#define No cout << "No" << "\n"// NOの短縮
#define rtr0 return(0)//return(0)の短縮
#define gyakugen(x) modpow(x,mod - 2,mod);
#define agyakugen(x) modpow(x,amod - 2,amod);
#define st(A) sort(A.begin(),A.end());
#define rst(A) sort(A.rbegin(),A.rend());
using namespace std;
//using namespace ranges;
using ll = long long;//63bit型整数型
using ld = long double;//doubleよりも長い値を保存できるもの
using ull = unsigned long long;//符号がない64bit型整数
ll mod = 998244353;
ll amod = 1000000007;
ll MINF = -5000000000000000000;
ll INF = 5000000000000000000;
ll inf = 2000000000;
ll minf = -2000000000;
ll BAD = -1;
ll zero = 0;
ld EPS = 1e-10;
int main(){
ll T;
cin >> T;
map<tuple<ll,ll,ll,ll,ll,ll,ll,ll,ll,ll>,ll>ans;
for(int i = 0;i*i<=1e9;i++){
    string s = to_string(i*i);
    tuple<ll,ll,ll,ll,ll,ll,ll,ll,ll,ll>X;
    for(int ii = 0;ii<s.size();ii++){
        ll x = s[ii]-'0';
        if(x==0)get<0>(X)++;
        if(x==1)get<1>(X)++;
        if(x==2)get<2>(X)++;
        if(x==3)get<3>(X)++;
        if(x==4)get<4>(X)++;
        if(x==5)get<5>(X)++;
        if(x==6)get<6>(X)++;
        if(x==7)get<7>(X)++;
        if(x==8)get<8>(X)++;
        if(x==9)get<9>(X)++;   
    }
    if(!ans.count(X))ans[X]=min((ll)(i*i),INF);
}
//cout << ans[{0,0,0,0,0,0,0,0,0,0}]<<"\n";
while(T--){
    ll N;
    cin >> N;
    string s = to_string(N);
    tuple<ll,ll,ll,ll,ll,ll,ll,ll,ll,ll>Y ={0,0,0,0,0,0,0,0,0,0};
    for(int ii = 0;ii<s.size();ii++){
        ll x = s[ii]-'0';
        if(x==0)get<0>(Y)++;
        if(x==1)get<1>(Y)++;
        if(x==2)get<2>(Y)++;
        if(x==3)get<3>(Y)++;
        if(x==4)get<4>(Y)++;
        if(x==5)get<5>(Y)++;
        if(x==6)get<6>(Y)++;
        if(x==7)get<7>(Y)++;
        if(x==8)get<8>(Y)++;
        if(x==9)get<9>(Y)++;   
    }
    //cout << get<0>(Y)<<" "<<get<1>(Y)<<"\n";
    ll res = INF;
    ll p = get<0>(Y);
    for(int i = p;i>=0;i--){
        get<0>(Y)=i;
        if(ans.count(Y))res = min(ans[Y],res);
    }
    if(res==INF)cout<<-1<<"\n";
    else cout<<res<<"\n";
}
}