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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    constexpr int r = 32000;
    vector<int> a(r + 1);
    for(int i = 1; i <= r; i++) a[i] = i * i;
    int T;
    cin >> T;
    while(T--){
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        int ans = -1, v;
        do{
            v = stoi(s);
            if(binary_search(a.begin(), a.end(), v)){
                ans = v;
                break;
            }
        }while(next_permutation(s.begin(), s.end()));
        cout << ans << '\n';
    }
}