#include<bits/stdc++.h>
using namespace std;
const int inf=1e6;
bool vis[inf+5];
int n,t;
int main(){
	memset(vis,true,sizeof(vis));
	vis[0]=vis[1]=false;
	for(int i=2;i*i<=inf;i++)if(vis[i]){
		for(int k=i;k*i<=inf;k++){
			vis[k*i]=false;
		}
	}
	cin>>t;
	while(t--){
		cin>>n;
		int tmp=1,ans=0;
		while(true){
			if(n<2){
				cout<<-1<<'\n';
				break;
			}
			if(vis[n]){
				cout<<ans+1<<'\n';	
				break;
			}
			n-=tmp;
			tmp*=2;
			ans++;
		}
	}
	return 0;
}