#include <bits/stdc++.h>

using namespace std;

int main() {
    unordered_map<long long, long long> mp;
    for (int k = 1; k <= 10; k++) {
        long long low = 1;
        if (k > 1) {
            low = 1;
            for (int i = 0; i < k-1; i++) {
                low *= 10;
            }
        }
        long long high = low * 10;
        long long r_min = (long long)sqrt((double)low);
        if (r_min * r_min < low) {
            r_min++;
        }
        long long r_max = (long long)sqrt((double)(high - 1));

        for (long long r = r_min; r <= r_max; r++) {
            long long X = r * r;
            vector<int> count_x(10, 0);
            long long temp = X;
            while (temp) {
                count_x[temp % 10]++;
                temp /= 10;
            }

            for (int t = 0; t <= 10 - k; t++) {
                vector<int> count_new = count_x;
                count_new[0] += t;
                long long state = 0;
                for (int i = 0; i < 10; i++) {
                    state = state * 11 + count_new[i];
                }
                if (mp.find(state) == mp.end()) {
                    mp[state] = X;
                }
            }
        }
    }

    int t;
    cin >> t;
    
    while (t--) {
        int N;
        cin >> N;
        vector<int> cnt(10);
        long long temp = N;
        while (temp) {
            cnt[temp % 10]++;
            temp /= 10;
        }
        long long state_n = 0;
        for (int i = 0; i < 10; i++) {
            state_n = state_n * 11 + cnt[i];
        }
        if (mp.find(state_n) != mp.end()) {
            cout << mp[state_n] << endl;
        } else {
            cout << -1 << endl;
        }
    }
    
    return 0;
}