#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,T;
signed main() {
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--) {
		cin>>k;
		if(k==0) {
			cout<<"NO!\n";
		} else if(k%2==1) {
			cout<<1<<endl;
		} else {
			if(k%4==0) {
				if(k%16==0) {
					cout<<5<<endl;
				} else if(k%8==0) {
					cout<<4<<endl;
				} else {
					cout<<3<<endl;
				}
			} else {
				cout<<2<<endl;
			}
		}
	}
	return 0;
}