#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10; 
int a[N];
bool st[N];
vector<int> p;
void get(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!st[i]) p.push_back(i);
		for(int j=0;p[j]<=n/i;j++)
		{
			st[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
}
int main()
{
	int t=1;
	get(N-1);
	for(int i=0;i<=20;i++)
	{
		a[t]=i;
		t*=2;
	}
	cin>>t;
	while(t--)
	{
		int x;
		cin>>x;
		int cnt=0;
		for(int i=p.size()-1;i>=0;i--)
		{
			if(x>=p[i])
			{ 
				int k=x-p[i];
				if(k==0)
				{
					cout<<1<<endl;
					cnt++;
					break;	
				} 
				if(a[k+1]!=0)
				{
					cout<<a[k+1]+1<<endl;
					cnt++;
					break;
				}
			}
		}
		if(cnt==0)
		{
			cout<<-1<<endl;
		}
	}
	return 0;
}