#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})
#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define WTHI(v) {unsigned _z=v,_n=0;long _d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(long*)wp=_d;wp+=_n;}
#define WTLO(v) {unsigned _z=v,_n=8;long _d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(long*)wp=_d;wp+=8;}
#define wt(v) if(v>=100000000){WTHI(v/10);*wp++=v%10+'0';}else{WTHI(v);}
#define repeat(e) for(typeof(e)_=e;_--;)
#define chmin(v,a) (v=v<=a?v:a)

#define HASH_BITS 15
#define HASH_N    (1<<HASH_BITS)
#define HASH_MASK (HASH_N-1)
long hash[HASH_N];

int hash_add(long x){
	int h=x&HASH_MASK;
	while(1){
		if(hash[h]==0){
			hash[h]=x;
			return h;
		}
		if(hash[h]==x){
			return -1;
		}
		h=h+1&HASH_MASK;
	}
}

int hash_get(long x){
	int h=x&HASH_MASK;
	while(1){
		if(hash[h]==0){
			return -1;
		}
		if(hash[h]==x){
			return h;
		}
		h=h+1&HASH_MASK;
	}
}

char wbuf[1<<25];
long po10[10];
int s[HASH_N];

void f0(){
	long p=1;
	for(int i=0;i<10;++i){
		po10[i]=p;
		p*=10;
	}
}

void f1(){
	for(int i=1;i<31623;++i){
		int j=i*i;
		long k=0;
		while(j){
			k+=po10[j%10];
			j/=10;
		}
		int h=hash_add(k);
		if(h>=0){
			s[h]=i*i;
		}
	}
}

void f2(){
	char*wp=wbuf;
	rd_init();
	int t=rd();
	repeat(t){
		long k=0;
		int z=0;
		for(int c;c=*rp++-'0',c>=0;){
			k+=po10[c];
			z+=!c;
		}
		int a=1<<30;
		for(;z>=0;--z){
			int h=hash_get(k);
			if(h>=0){
				chmin(a,s[h]);
			}
			--k;
		}
		if(a>=1<<30){
			*wp++='-';
			*wp++='1';
		}else{
			wt(a);
		}
		*wp++='\n';
	}
	write(1,wbuf,wp-wbuf);
}

int main(){
	f0();
	f1();
	f2();
	_exit(0);
}