题目
3.2 编程题 2 试题名称：挑战怪物
时间限制：1.0 s
内存限制：512.0 MB
3.2.1 题面描述 小杨正在和一个怪物战斗，怪物的血量为 ，只有当怪物的血量恰好为 时小杨才能够成功击败怪物。 小杨有两种攻击怪物的方式：
1.物理攻击。假设当前为小杨第 次使用物理攻击，则会对怪物造成 点伤害。
2. 魔法攻击。小杨选择任意一个质数 （ 不能超过怪物当前血量），对怪物造成 点伤害。由于小杨并不擅长魔 法，他只能使用至多一次魔法攻击。 小杨想知道自己能否击败怪物，如果能，小杨想知道自己最少需要多少次攻击。
3.2.2 输入格式 第一行包含一个正整数 ，代表测试用例组数。 接下来是 组测试用例。对于每组测试用例，第一行包含一个正整数 ，代表怪物血量。
3.2.3 输出格式 对于每组测试用例，如果小杨能够击败怪物，输出一个整数，代表小杨需要的最少攻击次数，如果不能击败怪物， 输出 。
样例输入1
3
6
188
9999
样例输出1
2
4
-1
3.2.4 样例1 对于第一组测试用例，一种可能的最优方案为，小杨先对怪物使用魔法攻击，选择质数 造成 点伤害，之后对怪 物使用第 次物理攻击，造成 点伤害，怪物血量恰好为 ，小杨成功击败怪物。
/CODE/
#include<bits/stdc++.h>
using namespace std;
bool prime[100000];
void fi(int n){
// cout<<1<<endl;
prime[0]=prime[1]=false;
for( int i=2;i<n;i++ )prime[i]=1;
for( long long i=2;i<n;i++ ){
if( prime[i]&&i*i>n )continue;
for( int j=i*i;j<=n;j+=i ){
prime[j]=false;
}
}
}
int main(){
fi(10000);
int t;
cin>>t;
while(t--){
int x;
cin>>x;
int tx=1;
int ans=0;
while(true){
// cout<<"ans:"<<ans<<endl;
if( prime[x] ){
ans++;
x-=prime[x];
break;
}
x-=tx;
ans++;
if( x==0 ){
// cout<<"YES"<<endl;
cout<<ans<<endl;
break;
}else if( x<0 ){
// cout<<"NO"<<endl;
cout<<-1<<endl;
break;
}
tx*=2;
}
// cout<<ans<<endl;
}
return 0;
}