#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
vector<bool> isPrime(100003,true);
vector<int>primes;
void sieve(int n) {
	isPrime[1]=0;
	for(int i=2; i<=n; i++) {
		if(isPrime[i]) {
			primes.push_back(i);
		}
		for(int j=0; i*primes[j]<=n; j++) {
			isPrime[i*primes[j]]=0;
			if(i%primes[j]==0) break;
		}
	}
}
int main() {
	sieve(100000);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int i;
        if(isPrime[n]){
            cout<<1<<endl;
            continue;
        }
		for(i=0;;){
			int u=pow(2,i);
			if(n-u<0){
				cout<<-1<<endl;
				break;
			}
			if(isPrime[n-u]){
				i+=2;
				cout<<i<<endl;
				break;
			}
			n-=u;
			i++;
		}
	}
	return 0;
}

找不出问题，求大佬帮帮忙