#include <iostream>
using namespace std;
int f(int a) {
	if (a == 2 || a == 1)return 1;
	if (a % 2 == 0)return 0;

	for (int i = 3; i * i <= a; i += 2) {
		if (a % i == 0) {
			return 0;
		}
	}
	return 1;
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;//n=9
		cin >> n;
		int n1 = n + 1;//n1=10
		int m = 0;
		int sum = 1;
		int fl = 0;
		if (f(n) == 1) { //是质数
			cout << 1 << endl;
			fl = 1;
		} else if (n1 % 2 == 0) {
			while (n1 % 2 == 0) {
				n1 /= 2;
				m++;
			}
			if (n1 == 1) {
				cout << m << endl;
				fl = 1;
				continue;
			} else {//n1=5
				if (n1 != 1) {
					n1 = n - 1;
					m = 0;
					while (n1 % 2 == 0) {
						n1 /= 2;
						m++;

					}
					if (n1 == 1) {
						cout << m + 1 << endl;
						fl = 1;
					}
				}
				
			}
		} else {
			for (int i = 1; i <= n / 2; i++) {
				sum *= 2;
				if (f(n + 1 - sum) == 1 && fl != 1) {
					cout << i + 1 << endl;
					fl = 1;
				}
			}
		}
		if (fl == 0) {
			cout << -1 << endl;
		}
		sum = 1;
		fl = 0;
		m = 0;





	}
	return 0;
}