#include<bits/stdc++.h>
using namespace std;
int q,n,ans=0;
bool isprime(int n){
	if(n<2) return 0;
	for(int i=2;i<=n/i;i++){
		if(n%i==0) return 0;
	}
	return 1;
}
int main(){
	cin>>n;
	while(q--){
		cin>>n;
		for(int i=n;i>=0;i--){
			if(isprime(i)){
				n-=i;
				ans=1;
				break;
			}
		}
		for(int i=1;;i++){
			n-=pow(2,i-1);
			ans++;
			if(n==0){
				cout<<ans<<endl;
				break;	
			}
			if(n<=0){
				cout<<"-1"<<endl;
				break;
			}
		}
	}	
	return 0;
}