#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;
vector<ll>randomhash = {(ll)1e9 + 7,(ll)1e9 + 801,((ll)1e8 * 8) + 29,((ll)1e8 * 7) + 159,((ll)1e8 * 9) + 221};
vector<ll>tate = {0,-1,0,1};//グリッド上の全探索時の四方向の上下のチェック
vector<ll>yoko = {1,0,-1,0};//グリッド上の全探索時の四方向の右左のチェック
vector<ll>eightx = {0,-1,-1,-1,0,1,1,1};//グリッド上の全探索時の八方向の上下のチェック
vector<ll>eighty = {1,1,0,-1,-1,-1,0,1};//グリッド上の全探索時の八方向の右左のチェック
vector<ll>hexsax = {0,1,1,0,-1,-1};
vector<ll>hexsay = {1,1,0,-1,-1,0};
//返り値は素数のリスト。
vector < bool > isprime;
vector < ll > Era(int n){//書き方 vector<ll>[] = Era(x); とやるとxまでの素数が出てくる。
	isprime.resize(n, true);
	vector < ll > res;
	isprime[0] = false;
	isprime[1] = false;
	for(ll i = 2; i < n; ++i) isprime[i] = true;
	for(ll i = 2; i < n; ++i) {
		if(isprime[i]) {
			res.push_back(i);
			for(ll j = i * 2; j < n; j += i) isprime[j] = false;
		}
	}
	return res;
}
//　　　　　　素数判定 21~35
ull modmul(ull a,ull b,ull mod) {
    return (__uint128_t)a*b%mod;
}
ll modpow(ll a, ll n, ll mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

long long npow(long long a, long long n){
    long long res = 1;
    while (n > 0) {
		if (n & 1) res = res * a;
		a = a * a;
		n >>= 1;
	}
	return res;
}
//     モッドを使った累乗
long long isqrt(long long num){
    return((long long)sqrtl(num));
}
ld get_theta(ld px,ld py,ld fx,ld fy,ld sx,ld sy){
    ld fxv = fx-px;
    ld fyv = fy-py;
    ld sxv = sx-px;
    ld syv = sy-py;
    ld fsv = fxv*sxv + fyv*syv;
    ld pfs = (ld)sqrt(fxv*fxv+fyv*fyv);
    ld pss = (ld)sqrt(sxv*sxv+syv*syv);
    return acos(fsv/(pfs*pss))*180/M_PI;
};
ld Euclidean_distance(ll x1,ll y1,ll x2,ll y2){
    ld x = abs((ld)x1 - (ld)x2);
    ld y = abs((ld)y1 - (ld)y2);
    return sqrt((x*x) + (y*y));
};
ll Manhattan_distance(ll x1,ll y1,ll x2,ll y2){
    return abs(x1-x2)+abs(y1-y2);
};
void change_bit(ll N,ll start,vector<ll>&X){
    for(ll i = start;i>=0;i--){
        ll a = npow(2,i);
        if(N/a==1){
            X[i]=1;
            N-=a;
        }
    }
}
void Run_Length_Encoding(vector<ll>A,vector<pair<ll,ll>>&RLE){
    RLE.push_back({A[0],1});
    ll N = A.size();
    for(int i = 1;i<N;i++){
        if(RLE[RLE.size()-1].first==A[i])RLE[RLE.size()-1].second++;
        else RLE.push_back({A[i],1});
    }
}
bool is_in_grid(ll i,ll ii,ll H,ll W){
    bool res = false;
    if(i>=0&&i<H&&ii>=0&&ii<W)res=true;
    return res;
}
template<class T>
struct rolling_hash{
    vector<ull>Power,hash,InvPower;
    ll B = 0;
    ll MOD = 0;
    void set_number(ll base,ll mod){
        B = base;
        MOD = mod;
    }
    void do_hash(const T &S) {
        ll N = S.size();
        Power.resize(N+1);
        InvPower.resize(N+1);
        hash.resize(N+1);
        Power[0] = 1;
        InvPower[0] = 1;
        for (ll i = 0;i<N;i++) {
            Power[i + 1] = modmul(Power[i],B,MOD);
            InvPower[i + 1] = modpow(Power[i+1],MOD-2,MOD);
            hash[i + 1] = (hash[i] + modmul(S[i], Power[i],MOD))%MOD;
        }
    }
    ll get_hash(ll l, ll r) {
        ull res = (hash[r]+MOD-hash[l])%MOD;
        res = modmul(res,InvPower[l],MOD);
        return res;
    }
};
template<class T>
struct combination{
  public:
    vector<T>factorial;
    ll MOD;
    ll N;
    void reset(T n,T mod){
        N = n+1;
        factorial.assign(N,1);
        MOD = mod;
    }
    void calu(){
        for(ll i = 1;i<N;i++){
            factorial[i] = (factorial[i-1]*(i))%MOD;
        }
    }
    T get(T n, T r){
        ll a = factorial[n];
        ll b = (factorial[r]*(factorial[n-r]))%MOD;
        b = modpow(b,MOD - 2,MOD);
        return (a*b)%MOD;
    }
};
template<class T>
struct dijkstra{
  public:
	vector<vector<pair<T,T>>>graph;
	vector<T>ans;
	priority_queue<pair<T,T>,vector<pair<T,T>>,greater<pair<T,T>>>pq;
    void do_dijkstra(T start){//頂点xからダイクストラを行う
		pq.push({0,start});
		ans[start] = 0;
		while(true){
			if(pq.empty())break;
			T cost = pq.top().first;
			T vertex = pq.top().second;
			pq.pop();
            if (cost > ans[vertex]) continue; 
			for(T i = 0;i<graph[vertex].size();i++){
				T nextvertex = graph[vertex][i].first;
				T nextcost = graph[vertex][i].second + cost;
				if(ans[nextvertex] <= nextcost)continue;
					ans[nextvertex] = nextcost;
					pq.push({nextcost,nextvertex});
			}
		}
	}
	void make_indirectedgraph(T u,T v,T cost){//無向辺のグラフ作成
		graph[u].push_back({v,cost});
		graph[v].push_back({u,cost});
	}
	void make_directedgraph(T u,T v,T cost){//有向辺のグラフ作成
		graph[u].push_back({v,cost});
	}
	T output(T end){//答えを出す
		return ans[end];
	} 
	void reset(T N){//リセット
		graph.assign(N, {});
        ans.assign(N, INF);
	}
};
template<class T>
struct unionfind {
public:
    vector<T> parent, rank;
    void reset(T N) { // 初期化
        parent.resize(N);
        rank.assign(N, 1); // 各集合のサイズを 1 にする
        for (T i = 0; i < N; i++) parent[i] = i;
    }
    T leader(T x) { // 経路圧縮による親の取得
        if (parent[x] == x) return x;
        return parent[x] = leader(parent[x]); // 経路圧縮
    }
    void marge(T x, T y) { // ランクによるマージ
        T a = leader(x), b = leader(y);
        if(a!=b){
            if (rank[a] < rank[b]) swap(a, b);
            parent[b] = a;
            rank[a] += rank[b]; // サイズを更新    
        }
    }
    bool same(T x, T y) { // 同じ集合か判定
        return leader(x) == leader(y);
    }
    T size(T x) { // 集合のサイズを取得
        return rank[leader(x)];
    }
    void check(T N) { // デバッグ用: 親の確認
        for (T i = 0; i < N; i++) cout << parent[i] << " ";
        cout << "\n";
    }
};
//セグ木
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
    public:
        segtree() : segtree(0) {}
        segtree(int n) : segtree(std::vector<S>(n, e())) {}
        segtree(const std::vector<S>& v) : _n(int(v.size())){
            log = ceil_pow2(_n);
            size = 1 << log;
            d = std::vector<S>(2 * size, e());
            for (int i = 0; i < _n; i++) d[size + i] = v[i];
            for (int i = size - 1; i >= 1; i--) {
                update(i);
            }
        }
  
        void set(int p, S x) {
            assert(0 <= p && p < _n);
            p += size;
            d[p] = x;
            for (int i = 1; i <= log; i++) update(p >> i);
        }
  
        S get(int p) {
            assert(0 <= p && p < _n);
            return d[p + size];
        }
  
        S prod(int l, int r) {
            assert(0 <= l && l <= r && r <= _n);
            S sml = e(), smr = e();
            l += size;
            r += size;
  
            while (l < r) {
                if (l & 1) sml = op(sml, d[l++]);
                if (r & 1) smr = op(d[--r], smr);
                l >>= 1;
                r >>= 1;
            }
            return op(sml, smr);
        }
  
        S all_prod() { return d[1]; }
  
        template <bool (*f)(S)> int max_right(int l) {
            return max_right(l, [](S x) { return f(x); });
        }
        template <class F> int max_right(int l, F f) {
            assert(0 <= l && l <= _n);
            assert(f(e()));
            if (l == _n) return _n;
            l += size;
            S sm = e();
            do{
                while (l % 2 == 0) l >>= 1;
                if (!f(op(sm, d[l]))) {
                    while (l < size) {
                        l = (2 * l);
                        if (f(op(sm, d[l]))) {
                            sm = op(sm, d[l]);
                            l++;
                        }
                    }
                    return l - size;
                }
                sm = op(sm, d[l]);
                l++;
            }while ((l & -l) != l);
            return _n;
        }
  
        template <bool (*f)(S)> int min_left(int r) {
            return min_left(r, [](S x) { return f(x); });
        }
        template <class F> int min_left(int r, F f) {
            assert(0 <= r && r <= _n);
            assert(f(e()));
            if (r == 0) return 0;
            r += size;
            S sm = e();
            do{
                r--;
                while (r > 1 && (r % 2)) r >>= 1;
                if (!f(op(d[r], sm))) {
                    while (r < size) {
                        r = (2 * r + 1);
                        if (f(op(d[r], sm))) {
                            sm = op(d[r], sm);
                            r--;
                        }
                    }
                    return r + 1 - size;
                }
                sm = op(d[r], sm);
            }while ((r & -r) != r);
            return 0;
        }
  
    private:
        int _n, size, log;
        std::vector<S> d;
  
        void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
        int ceil_pow2(int n) {
            int x = 0;
            while ((1U << x) < (unsigned int)(n)) x++;
            return x;
        }
};

//遅延セグ木
template <class S,S (*op)(S, S),S (*e)(),class F,S (*mapping)(F, S),F (*composition)(F, F),F (*id)()>
struct lazy_segtree {

    public:
        lazy_segtree() : lazy_segtree(0) {}
        lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
        lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
            log = ceil_pow2(_n);
            size = 1 << log;
            d = std::vector<S>(2 * size, e());
            lz = std::vector<F>(size, id());
            for (int i = 0; i < _n; i++) d[size + i] = v[i];
            for (int i = size - 1; i >= 1; i--) {
                update(i);
            }
        }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

    private:
        int _n, size, log;
        std::vector<S> d;
        std::vector<F> lz;
        int ceil_pow2(int n) {
            int x = 0;
            while ((1U << x) < (unsigned int)(n)) x++;
            return x;
        }
        void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
        void all_apply(int k, F f) {
            d[k] = mapping(f, d[k]);
            if (k < size) lz[k] = composition(f, lz[k]);
        }
        void push(int k) {
            all_apply(2 * k, lz[k]);
            all_apply(2 * k + 1, lz[k]);
            lz[k] = id();
        }
};
struct Euler_Tour{//最小共通祖先,部分木のコスト,通り道のコスト,のグラフを作る部分(オイラーツアー)
    //必要なもの集
    //セグ木は2*Nがベース
    //LCA(最小共通祖先)discovery,finish,visit,high
    //とある頂点xを根とする部分木の範囲 discovery,finish
    //頂点xを根とする部分木の辺と頂点のコストの総和 discovery,finish,vcost1,ecost1
    //頂点xを根とする頂点yまでの最短の辺と頂点のコストの総和 discovery,finish,vcost2,ecost2
    vector<int>discovery,finish,visit,high,vweight,vcost1,vcost2,ecost1,ecost2;
    vector<int>other;
    vector<vector<pair<int,int>>>graph;
    int cnt;
    int othercnt;
    void reset(ll N){
        cnt = 0;
        othercnt = 0;
        other.assign(2*N,0);
        discovery.assign(N,inf);
        finish.assign(N,minf);
        vweight.assign(N,0);
        graph.assign(N,vector<pair<int,int>>(0));
        visit.assign(2*N,0);
        high.assign(2*N,0);
        vcost1.assign(2*N,0);
        vcost2.assign(2*N,0);
        ecost1.assign(2*N,0);
        ecost2.assign(2*N,0);
    };
    void make_graph(ll u,ll v,ll cost){
        if(max(u,v)>graph.size()){
            cout << "not reset or out of range" << "\n";
            return;
        }
        graph[u].push_back({v,cost});
        graph[v].push_back({u,cost});
    }
    void set_vweight(ll vertex,ll cost){
        vweight[vertex]+=cost;
    }
    void DFS(ll vertex,ll nowdepth,ll cost){
        if(discovery[vertex]==inf){
            vcost1[cnt]=vweight[vertex];
            vcost2[cnt]=vweight[vertex];
        }
        else{
            vcost1[cnt]=0;
            vcost2[cnt]=0;
        }
        ecost1[cnt]=cost;
        ecost2[cnt]=cost;
        discovery[vertex]=min(discovery[vertex],cnt);
        visit[cnt]=vertex;
        high[cnt]=nowdepth;
        for(int i = 0;i<graph[vertex].size();i++){
            int x = graph[vertex][i].first;
            int nextcost = graph[vertex][i].second;
            if(discovery[x]!=inf&&graph[vertex].size()==1)othercnt++;
            other[cnt]=othercnt;
            if(discovery[x]==inf){
                cnt++;
                DFS(x,nowdepth+1,nextcost);
                cnt++;
                visit[cnt]=vertex;
                high[cnt]=nowdepth;
                vcost1[cnt]=0;
                ecost1[cnt]=0;
                vcost2[cnt]=vweight[x]*-1;
                ecost2[cnt]=nextcost*-1;
            }
            other[cnt]=othercnt;
        }
        finish[vertex]=cnt+1;
        return;
    }
    int get_size(){
        ll res = high.size()-1;
        return res;
    }
    int get_vcost1(ll i){
        return ecost1[i];
    }
    int get_vcost2(ll i){
        return vcost2[i];
    }
    int get_ecost1(ll i){
        return vcost1[i];
    }
    int get_ecost2(ll i){
        return ecost2[i];
    }
    int get_high(ll i){
        return high[i];
    }
    int get_visit(ll i){
        return visit[i];
    }
    int get_discovery(ll i){
        return discovery[i];
    }
    int get_finish(ll i){
        return finish[i];
    }
};
//遅延セグ木のベース
//型
using segS = ll;
segS oop(segS a,segS b){
    return max(a,b);
}
segS ee(){
    return 0;
}
/*struct segS{
    ll mi = 0;
    ll ma = 0;
};
segS oop(segS a,segS b){
    segS res;
    res.mi = min(a.mi,b.mi);
    res.ma = max(a.ma,b.ma);
    return res;
}
segS ee(){
    segS res;
    res.mi = INF;
    res.ma = MINF;
    return res;
}*/

//using lazyS = ll;
using lazyS = ll;
using lazyF = ll;
lazyS e(){
    lazyS res;
    res = 0;
    return res;
}//範囲外などを起こしてしまったときの返り値
lazyS op(lazyS a, lazyS b){
    lazyS res;
    res = a+b;
    return res; 
}//操作したいこと
lazyS mapping(lazyF f, lazyS x){ 
    x*=f;
    return x; 
}//下まで伝播させたいこと
lazyF composition(lazyF f, lazyF g){ return g *= f; }//まとめてやった場合おこしたいこと
lazyF id(){ return 1; }//遅延セグ木のベース
/*
using lazyS = ll;
using lazyF = ll;
lazyS e(){ return 0;}//範囲外などを起こしてしまったときの返り値
lazyS op(lazyS a, lazyS b){ return a+b; }//操作したいこと
lazyS mapping(lazyF f, lazyS x){ return x /= f; }//下まで伝播させたいこと
lazyF composition(lazyF f, lazyF g){ return g /= f; }//まとめてやった場合おこしたいこと
lazyF id(){ return 1; }//遅延セグ木のベース
*/
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";
}
}