- 题意:5可以有两种 2 3, 5.质数之和
- 因为23 32是重复的
- 由于数据小, 如果数据小于100,连打表都不用
#include<bits/stdc++.h>
using namespace std;
int t, n, m;
int dp[100], step, cnt;
int judge(int u){
for(int i = 2; i <= sqrt(u); i ++)
if(u%i==0)return 0;
return 1;
}
void init(){
for(int i = 2; i <= 150; i ++){
if(judge(i))
dp[++step] = i;
}
}
void dfs(int ans, int n, int k){
if(ans > n)return ;
if(ans == n){
cnt ++;
return ;
}
for(int i = k; i <= step; i ++){
dfs(ans+dp[i],n, i);
}
}
int main(){
ios::sync_with_stdio(false);
init();
cin >> t;
while(t --){
cin >> n;
cnt = 0;
dfs(0, n, 1);
cout << cnt << endl;
}
return 0;
}