#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,T,k,i;
bool flag=false;
bool is_p(int n){
    if(n==2) return 1;
    if(n%2==0) return 0;
    for(int i=3;i*i<=n;i++){
        if(n%i==0) return 0;
    }
    return 1;
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n;
		flag=false;
		for(int i=n;i>=2;i--){
			if(is_p(i)){
				n-=i;
                flag=true;
				break;	
			} 
		}
		//cout<<n<<endl;
		if(n==0){
			cout<<1<<endl;
			continue;
		}	
		for(i=1;;i++){
			//cout<<pow(2,i-1)<<endl;
			n-=pow(2,i-1);
			if(n<=0) break;
		}
		if(n==0&&flag) cout<<i+1<<endl;
        else if(n==0&&!flag) cout<<i<<endl;
		else cout<<"-1"<<endl;	
	}
	return 0;
}