#include<bits/stdc++.h>
using namespace std;
bool isPrime(int num){
	if(num<=1)
		return false;
	if(num==2)
		return true;
	if(num%2==0)
		return false;
	for(int i=3;i<=(int)sqrt(num);i+=2)
		if(num%i==0)
			return false;
	return true;
}
int t,sum_physical[40];
int main(){
	cin>>t;
	sum_physical[0]=0;
	for(int i=1;i<31;i++)
		sum_physical[i]=sum_physical[i-1]+(2*i-1);
	while(t--){
		int h;
		cin>>h;
		int min_attacks=-1;
		for(int k=0;k<31;k++){
			int S=sum_physical[k];
			if(S>h)
				break;			
			int remaining=h-S;
			if(!remaining)
				if(min_attacks==-1||k<min_attacks)
					min_attacks=k;
			else{
				if(isPrime(remaining)){
					int total=k+1;
					if(min_attacks==-1||total<min_attacks)
						min_attacks=total;
				}
			}
		}
		cout<<min_attacks<<endl;
	}
	return 0;
}