#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,ans=0;
	cin>>n;
	bool zs[100000]={0};
	for(int i=2;i<=100000;i++){
		zs[i]=1;
	}
	for(int i=2;i*i<=100000;i++){
		if(zs[i]){
			for(int j=2*i;j<=100000;j+=i){
				zs[j]=0;
			}
		}
	}
	for(int q=0;q<n;q++){
		int h;
		cin>>h;
		while(true){
			q++;
			if(zs[h]==1){
				ans++;
				printf("%d",ans);
				cout<<endl;
				break;
			}
			else{
				h-=pow(2,q-1);
				ans++;
			}
			if(h<0){
				cout<<"-1"<<endl;
				break;
			}
			if(h==0){
				cout<<ans<<endl;
				break;
			}
		}
		ans=0;
	}
	return 0;
}