/* -*- coding: utf-8 -*-
 *
 * 3204.cc:  No.3204 Permuted Integer - yukicoder
 */

#include<cstdio>
#include<cmath>
#include<unordered_map>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 1000000000;
const int MAX_M = 10;

/* typedef */

using ll = long long;
using umli = unordered_map<ll,int>;

/* global variables */

/* subroutines */

ll cs2bits(int cs[]) {
  ll bits = 0;
  for (int i = 9; i >= 0; i--) bits = (bits << 4) | cs[i];
  return bits;
}

/* main */

int main() {
  umli cache;
  int cs[10];
  
  for (int y = 1; y * y <= MAX_N; y++) {
    int x = y * y, m = 0;
    fill(cs, cs + 10, 0);
    while (x > 0) cs[x % 10]++, x /= 10, m++;

    ll bits = cs2bits(cs);
    while (m <= MAX_M) {
      if (! cache.count(bits)) cache[bits] = y * y;
      bits++, m++;
    }
  }
  
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int n;
    scanf("%d", &n);
    
    fill(cs, cs + 10, 0);
    while (n > 0) cs[n % 10]++, n /= 10;
    ll bits = cs2bits(cs);
    
    int minx = cache.count(bits) ? cache[bits] : -1;
    printf("%d\n", minx);
  }
  
  return 0;
}