#include<bits/stdc++.h>
using namespace std;
bool isprime(int n)
{
	if(n<2) return false;
    for(int i=2;i*i<=n;i++) 
	{
		if(n%i==0) return false;
	}
    return true;
}   
int main()
{
	int t,h;
	cin>>t;
	while(t--)
	{
		int temp,ac=h,cnt=1,sum=0; 
		bool flag=false;
		cin>>h;
		for(int i=h;i>=1;i--)
		{
			if(isprime(i)) 
			{
				cnt=1,sum=0;
				flag=false;
				temp=i;
				//cout<<temp<<"\n"; 
				ac = h-temp;
				while(1)
				{
					sum+=pow(2,cnt-1);
					if(sum==ac) 
					{
						cout<<cnt+1<<"\n";
						flag=true;
						break;
					}
					else if(sum>ac) 
					{
						flag=false;
						break;
					}
					cnt++;
				}
		    }
            if(flag==true) break;
		}
		if(flag==false)
		{
			cnt=1,sum=0;
			while(1)
			{
				sum+=pow(2,cnt-1);
				if(sum==h) 
				{
					cout<<cnt<<"\n";
					flag=true;
					break;
				}
				else if(sum>h) 
				{
					flag=false;
					break;
				}
				cnt++;
			}
			if(flag==false) cout<<-1<<"\n";	
		}   
	}
	return 0;
}