#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N=1e5+5;

int n;

bool zhi(int x)
{
	if(x<=1) return 0;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0) return 0;
	}
	return 1;
}

void solve()
{
	cin>>n;
	int i=1,cnt=0;
	do
	{
		n-=pow(2,i-1);
		cnt++;
		i++;
		if(zhi(n)==1)
		{
			cout<<cnt+1<<endl;
			return;
		}
	}while(n>0);
	if(n==0)
	{
		cout<<cnt<<endl;
		return;
	}
	else if(n<0)
	{
		cout<<-1<<endl;
		return;
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int T;
	cin>>T;

	while(T--) solve();

	return 0;
}

我是小蒟蒻，不喜勿喷