#include<iostream>
#include<cmath>
using namespace std;
bool isprime(int n)
{
	if(n<=1) return 0;
	if(n==2) return 1;
	if(n%2==0) return 0;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0) return 0;
	}
	return 1;
}
int main()
{
//	每次都使用物理攻击，
//	如果怪物血量是质数，使用魔法攻击一次。
//	如果怪物血量问还没有出现质数，那么就是不能击败怪兽。
	int T;
	cin>>T;
	while(T--)
	{
		int h;
		cin>>h;
		int cnt=0,k=0;
		while(h>=1)
		{
			if(isprime(h))//是质数用魔法攻击 
			{
				cnt++;//魔法攻击一次 
				cout<<cnt<<endl;
				break;
			}
			else if(h==0)
			{
				cout<<cnt<<endl;
				break;
			}
			else 
			{
				k++;
				h-=pow(2,k-1);
				cnt++;//物理攻击一次 
			}
		}
		if(h<0) cout<<-1<<endl;//不能打败 
	} 
	return 0;
}