奇迹
题目背景 相信奇迹的人，本身就和奇迹一样了不起。——笛亚 《星游记》
题目描述 我们称一个日期为一个八位数，第 1~4 位构成年，第 5~6 位构成月，第 7~8 位构成日，不足位数用 0 补足。同时，要求日期所代表的这一天真实存在，且年的范围为 1~9999。
出现奇迹的日期都存在相同的特点：由“日”组成的两位数，由“月+日”组成的四位数，由“年+月+日”组成的八位数均为质数。但并不是所有存在这样特点的日期都一定会出现奇迹。
现在，你得到了一个可能会出现奇迹的日期，然而不幸的是这个日期却是残缺的，八位中可能有若干位无法确定。你需要知道这个日期有多少种可能，这样你才能做好充足的准备去迎接奇迹的到来。
输入输出格式 输入格式： 本题有多组数据。
第一行一个正整数 TT，表示数据组数。
接下来的 TT 行，每行一个八位字符串。其中第 ii 位如果为 -，则表示日期的第 ii 位无法确定，否则表示日期的第 ii 位为字符串中第 ii 位上的数字。
输出格式： 对每组数据，一行一个整数，表示答案。
输入输出样例 输入样例#1： 复制 2 53-7-3-7 20190629 输出样例#1： 复制 6 0 说明 【样例 11 说明】
53-7-3-7 的 66 种可能的日期如下：
53070307 53070317 53170307 53370307 53570317 53770307 【数据规模与约定】
一共 1010 个测试点，记 cc 为八位字符串中 - 的个数。
对前 99 个测试点，在第 ii 个测试点中保证 c = i - 1c=i−1。
对 100\%100% 的数据保证 1 \le T \le 101≤T≤10。
#include <bits/stdc++.h>
#define re register
using namespace std;
int num[13],tmp[14],n,m,res,cnt,ans,prime[100000010];
bool is[100000010];
char c[101];
inline void solve() {
int ri,yue,nian;
num[2]=28;
nian=tmp[1]*1000+tmp[2]*100+tmp[3]*10+tmp[4];
yue=tmp[5]*10+tmp[6];
ri=tmp[7]*10+tmp[8];
if(nian%4==0&&nian%100!=0||nian%400==0) num[2]=29;
if(!nian) return;
if(!yue||yue>12) return;
if(!ri||ri>num[yue]) return;
int sum1=ri;
int sum2=yue*100+ri;
int sum3=nian*10000+yue*100+ri;
if(is[sum1]||is[sum2]||is[sum3]) return;
ans++;
}
inline void dfs(int x) {
if(x==9) {
solve();
return;
}
if(c[x]!='-') {
tmp[x]=c[x]-'0';
dfs(x+1);
}
else {
for ( re int i=0;i<=9;i++ ) {
tmp[x]=i;
dfs(x+1);
tmp[x]=0;
}
}
}
int main() {
num[1]=31;
num[2]=28;
num[3]=31;
num[4]=30;
num[5]=31;
num[6]=30;
num[7]=31;
num[8]=31;
num[9]=30;
num[10]=31;
num[11]=30;
num[12]=31;
is[1]=1;
for ( re int i=2;i<=100000005;i++ ) {
if(!is[i]) prime[++cnt]=i;
for ( re int j=1;j<=cnt;j++ ) {
if(prime[j]*i>100000005) break;
is[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
int q;
scanf("%d",&q);
while(q--) {
scanf("%s",c+1);
memset(tmp,0,sizeof(tmp));
ans=0;
dfs(1);
if(c[1]=='-'&&c[2]=='-'&&c[3]=='-'&&c[4]=='-'&&c[5]=='-'&&c[6]=='-'&&c[7]=='-'&&c[8]=='-') {
puts("55157");
continue;
}
printf("%d\n",ans);
}
return 0;
}