cmmp

#include <fstream>
using namespace std;
ifstream in("cmmp.in");
ofstream out("cmmp.out");
int cifre(long long n)
{
    int cnt=0;
    while(n)
    {
        n/=10;
        cnt++;
    }
    return cnt;
}
long long rasp[100001];
int v[11];
void fa(long long num)
{
    int x=cifre(num),i,nr,j,num1=num;
    for(i=x; i>=1; i--)
    {
        v[i]=num1%10;
        num1/=10;
    }
    for(i=1; i<=x; i++)
    {
        nr=0;
        for(j=i; j<=x; j++)
        {
            nr=nr*10+v[j];
            if(nr>100000)
                break;
            if(rasp[nr]==-1)
                rasp[nr]=num;
        }
    }
}
int main()
{
    int n,x,i;
    in>>n;
    for(i=1; i<=100000; i++)
        rasp[i]=-1;
    for(i=1; i<=83667; i++)
        fa((long long)(i*i));
    for(i=1; i<=n; i++)
    {
        in>>x;
        out<<rasp[x]<<'\n';
    }
    return 0;
}