交上去好像全T了，但是把$1$到$20000$都测了一遍好像没发现超时问题.... ？

#include <bits/stdc++.h>
#define MAX 50005
using namespace std;
int f[MAX];
int p[MAX], r[MAX], w[MAX], l;
int n, s;
void era(){
	for(int i = 2; i <= MAX; i++)
		if(p[i] == 0){
			for(int j = i * 2; j <= MAX; j += i)
				p[j] = 1;
			l++;
			r[l] = i;
		}
}
int main(){
	memset(f, -1, sizeof f);
	era();
	f[0] = f[1] = w[0] = w[1] = 0;
	for(int i = 0; i <= MAX; i++){
		for(int j = 1; j <= l; j++){
			if(i + r[j] > MAX) break;
			if(f[i + r[j]] == -1)
				f[i + r[j]] = f[i] + 1;
			else{
				int a = (w[i + r[j]] == 0), b = (w[i] == 0);
				if(a + b == 1)
					f[i + r[j]] = min(f[i] + 1, f[i + r[j]]);
				else if(a + b == 2)
					f[i + r[j]] = f[i] + 1;
			}
			if(w[i] == 0){
				w[i + r[j]] = 1;
			}
		}
	}
	cin >> n;
	while(n--){
		cin >> s;
		if(w[s])
			cout << f[s] << "\n";
		else
			cout << "-1\n";
	}
	return 0;
}