#include <bits/stdc++.h>

using namespace std;
long long n,a,b[18]{0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536},ans=0;
bool f(int x)
{
	if(x<2)
	{
		return 0;
	}
	for (int i=1;i<=x/2;i++)
	{
		if(x%i==0)
		{
			return 0; 
		}
	}
	return 1;
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
    	ans=0;
    	cin>>a;
    	if(f(a)==1)
    	{
    		cout<<1;
    		
		}
    	for(int i=1;i<=17;i++)
    	{
    		a=a-b[i];
    		ans++;
    		if(a==0)
    		{
    			cout<<ans<<endl;
    			continue;
			}
    		if(f(a)==1)
    		{
    			a=0;
    			ans++;
    			cout<<ans<<endl;
    			continue;
			}
		}
		if(a<0)
		{
			cout<<"-1"<<endl;
		}
	}
	return 0;
}