#include<bits/stdc++.h>
using namespace std;
int n,t,jsq;
bool pd(int x){
	if(x==2||x==3) return 1;
	if(x%3==0||x%2==0||x==1) return 0;
	for(int i=5;i*i<=x;i+=2) if(x%i==0) return 0;
	return 1;
}
int main(){
	cin>>t;
	while(t--){
		jsq=0;
		cin>>n;
		for(int i=1;n!=0&&n>pow(2,i-1);i++){
			//cout<<"*";
			if(n==0) cout<<jsq<<'\n';
			if(pd(n)==1){
				i--;
				n=0;
				cout<<jsq+1<<'\n';	
			} 
			else {
				n=n-pow(2,i-1);
				jsq++;
			}
			
		}
		if(n>0) cout<<"-1\n";
	}
	return 0;
}