#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int ans[500005];
 
void precomp(){
	for(int i = 2; i <= 500000; i++)ans[i] = 1e13;
 
	ans[1] = 1;
	for(int i = 3; i <= 500000; i+=2){
		ans[i] = min(ans[i], ans[i-2]+1);
		for(int j = 3; i*j <= 500000 && j <= i; j++){
			ans[i*j] = min(ans[i*j], ans[j-2] + ans[i]);
		}
	}
 
	for(int i = 2; i <= 500000; i++)ans[i] = (ans[i] == 1e13? -1:ans[i]);
}
 
void fun(){
	int m;
	cin >> m;
	cout << ans[m] << '\n';
}
 
main() {
	precomp();
	int t; cin >> t;
	while(t--)fun();
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgaW50IGxvbmcgbG9uZwoKaW50IGFuc1s1MDAwMDVdOwoKdm9pZCBwcmVjb21wKCl7Cglmb3IoaW50IGkgPSAyOyBpIDw9IDUwMDAwMDsgaSsrKWFuc1tpXSA9IDFlMTM7CgkKCWFuc1sxXSA9IDE7Cglmb3IoaW50IGkgPSAzOyBpIDw9IDUwMDAwMDsgaSs9Mil7CgkJYW5zW2ldID0gbWluKGFuc1tpXSwgYW5zW2ktMl0rMSk7CgkJZm9yKGludCBqID0gMzsgaSpqIDw9IDUwMDAwMCAmJiBqIDw9IGk7IGorKyl7CgkJCWFuc1tpKmpdID0gbWluKGFuc1tpKmpdLCBhbnNbai0yXSArIGFuc1tpXSk7CgkJfQoJfQoJCglmb3IoaW50IGkgPSAyOyBpIDw9IDUwMDAwMDsgaSsrKWFuc1tpXSA9IChhbnNbaV0gPT0gMWUxMz8gLTE6YW5zW2ldKTsKfQoKdm9pZCBmdW4oKXsKCWludCBtOwoJY2luID4+IG07Cgljb3V0IDw8IGFuc1ttXSA8PCAnXG4nOwp9CgptYWluKCkgewoJcHJlY29tcCgpOwoJaW50IHQ7IGNpbiA+PiB0OwoJd2hpbGUodC0tKWZ1bigpOwp9

NgoxCjMKNQo3CjkKMjU=

6
1
3
5
7
9
25