40分求助!!!!!!!!!!!!!!!!

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int zs(int n){
	if(n<=1) return 0;
	for(int i=2;i*i<=n;i++){
		if(n%i==0) return 0;
	}
	return 1;
}
int main(){
	cin.tie(0);
	ll T,i,s;
	cin>>T;
	while(T--){
		ll h;
		s=1;
		cin>>h;
		i=0;
		while(h>0){
			if(zs(h)){
				cout<<i+1<<'\n';
				break;
			}
			h-=s;
			s*=2;
			i++;
		}
		if(zs(h)) continue;
		else if(h<0) cout<<-1;
		else cout<<i<<'\n';
	}
	return 0;
}