#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] = 1e9;
 
	ans[1] = 1;
	for(int i = 3; i <= 500000; i++){
		if(i>2)ans[i] = min(ans[i], ans[i-2]+1);
		if(i%3==0)ans[i] = min(ans[i], ans[i/3]+1);
 
		for(int j = 2; j*j <= i; j++){
			if(i%j==0)ans[i] = min(ans[i], ans[i/j] + ans[j-2]);
		}
	}
 
	for(int i = 2; i <= 500000; i++)ans[i] = (ans[i] == 1e9? -1:ans[i]);
}
 
void fun(){
	int m;
	cin >> m;
	cout << ans[m] << '\n';
}
 
main() {
	precomp();
	int t; cin >> t;
	while(t--)fun();
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgaW50IGxvbmcgbG9uZwoKaW50IGFuc1s1MDAwMDVdOwoKdm9pZCBwcmVjb21wKCl7Cglmb3IoaW50IGkgPSAyOyBpIDw9IDUwMDAwMDsgaSsrKWFuc1tpXSA9IDFlOTsKCQoJYW5zWzFdID0gMTsKCWZvcihpbnQgaSA9IDM7IGkgPD0gNTAwMDAwOyBpKyspewoJCWlmKGk+MilhbnNbaV0gPSBtaW4oYW5zW2ldLCBhbnNbaS0yXSsxKTsKCQlpZihpJTM9PTApYW5zW2ldID0gbWluKGFuc1tpXSwgYW5zW2kvM10rMSk7CgkJCgkJZm9yKGludCBqID0gMjsgaipqIDw9IGk7IGorKyl7CgkJCWlmKGklaj09MClhbnNbaV0gPSBtaW4oYW5zW2ldLCBhbnNbaS9qXSArIGFuc1tqLTJdKTsKCQl9Cgl9CgkKCWZvcihpbnQgaSA9IDI7IGkgPD0gNTAwMDAwOyBpKyspYW5zW2ldID0gKGFuc1tpXSA9PSAxZTk/IC0xOmFuc1tpXSk7Cn0KCnZvaWQgZnVuKCl7CglpbnQgbTsKCWNpbiA+PiBtOwoJY291dCA8PCBhbnNbbV0gPDwgJ1xuJzsKfQoKbWFpbigpIHsKCXByZWNvbXAoKTsKCWludCB0OyBjaW4gPj4gdDsKCXdoaWxlKHQtLSlmdW4oKTsKfQ==

NgoxCjMKNQo3CjkKMjU=

6
1
3
5
7
9
25