#include<stdio.h>
int main(){
	int T;
	scanf ("%d",&T);
	int num[10000];
	int n,m;
	while(T--){
		scanf("%d",&n);
		int flag=0,k,j;
		for(j=2;j<=n;++j){
		  int m=n;
		  int i=0;
		  while(m>0){
			num[i]=m%j;
			m/=j;
			++i;
		  }
		  if(num[0]==7&&num[1]==1&&i==2){
	         flag=1;
	         k=j;
	         break;
	      }
	   }
	   if(flag==1)
	      printf("%d\n",k);
	   else
	      printf("-1\n");
	}
}