AC

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int N;
	cin >> N;
	vector<int> nums(N);
	int max_num = 0;
	for (int i = 0; i < N; ++i) {
    	cin >> nums[i];
    	if (nums[i] > max_num) {
        	max_num = nums[i];
    	}
	}
	vector<bool> is_prime(max_num + 1, true);
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i * i <= max_num; ++i) {
    	if (is_prime[i]) {
        	for (int j = i * i; j <= max_num; j += i) {
            	is_prime[j] = false;
        	}
    	}
	}
	vector<int> primes;
	for (int i = 2; i <= max_num; ++i) {
    	if (is_prime[i]) {
        	primes.push_back(i);
    	}
	}
	vector<bool> win(max_num + 1, false);
	vector<int> steps(max_num + 1, 0);

	for (int n = 1; n <= max_num; ++n) {
    	bool can_win = false;
    	int min_step = INT_MAX;
    	int max_step = -1;

    	for (int p : primes) {
        	if (p > n) break;
        	int rem = n - p;
        	if (rem < 0) continue;

        	if (!win[rem]) {
            	can_win = true;
            	int current_step = 1 + steps[rem];
            	if (current_step < min_step) {
                	min_step = current_step;
            	}
        	} else {
            	int current_step = 1 + steps[rem];
            	if (current_step > max_step) {
                	max_step = current_step;
            	}
        	}
    	}

    	if (can_win) {
        	win[n] = true;
        	steps[n] = min_step;
    	} else {
        	win[n] = false;
        	steps[n] = (max_step == -1) ? 0 : max_step;
    	}
	}

	for (int x : nums) {
    	if (win[x]) {
        	cout << steps[x] << endl;
    	} else {
        	cout << -1 << endl;
    	}
	}
	return 0;
}