题目背景 相信奇迹的人，本身就和奇迹一样了不起。——笛亚 《星游记》
题目描述 我们称一个日期为一个八位数，第 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 ",ans); } return 0; }