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

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(int i = (a); i >= (b); i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
#define SZ(v) ((int)(v).size())

using lint = long long;
using ld = long double;

int INF = 2000000000;
lint LINF = 1000000000000000000;

struct SetupIo {
    SetupIo() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} setupio;

// a <- max(a, b)
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

// a <- min(a, b)
template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

void init(array<int, 10> &a) {
    rep(i, 10) {
        a[i] = 0;
    }
}

int main() {
    set<array<int, 10>> st;
    map<array<int, 10>, int> mp;
    for (int i = 1; i * i <= 1e9; i++) {
        string s = to_string(i * i);
        array<int, 10> a;
        init(a);
        for (char c : s) {
            a[c - '0']++;
        }
        if (mp.count(a)) {
        	chmin(mp[a], i * i);
        } else {
        	st.insert(a);
        	mp[a] = i * i;
        }
    }

    int T;
    cin >> T;
    map<array<int, 10>, int> memo;

    while (T--) {
        int N;
        cin >> N;
        string s = to_string(N);
        array<int, 10> a;
        init(a);
        for (char c : s) {
            a[c - '0']++;
        }
        if (memo.count(a)) {
            cout << memo[a] << "\n";
            continue;
        }
        int ans = INT_MAX;
        while (a[0] >= 0) {
            if (st.count(a)) {
                chmin(ans, mp[a]);
            }
            a[0]--;
        }
        if (ans == INT_MAX) {
            ans = -1;
        }
        memo[a] = ans;
        cout << ans << "\n";
    }
}