提交记录：AC on #3 #4 #5

#include<iostream>
#include<string>
#define gc getchar
using namespace std;
int T,a[10],otto,tn[9]={0,1,10,100,1000,10000,100000,1000000,10000000};
char c[10];
bool f[10005],vis[10005];
int b[10005],top;
bool is_prime(int x){//素数判定
	if(x<10000)return f[x];//小于10000直接用线性筛
    for(int i=2;i*i<=x;i++){
    	if(x%i==0)return 0;
	}
	return 1;
}
bool is_r(int x){//闰年判定
	return (x%400==0||(x%4==0&&x%100!=0));
}
void dfs(int sum,int d){
	int x=a[d+1];
	if(d==2&&(!is_prime(sum)||sum>31||sum==0))return;//判定日
	if(d==4){//判定月+日
		if(!is_prime(sum))return;
		if(sum>1231)return;
		if(a[d]==4||a[d]==6||a[d]==9||a[d]==11)if(sum%100>30)return;
		if(229<sum&&sum<300)return;
		if(a[3]==0&&a[4]==0)return;
		if(sum<32)return;
	}
	if(d==8){//判定年+月+日
		int u=sum/10000;
		if(u==0)return;
		if(sum%10000==229&&!is_r(u))return;
		otto+=is_prime(sum);
		//if(is_prime(sum))cout<<sum<<"\n";
		return;
	}
	if(x==-1){//如果是-枚举搜索
		int aa=0,bb=10;
		if(d+1==2)bb=4;
		else if(d+1==4)bb=2;
		for(int i=aa;i<bb;i++){
			a[d+1]=i;
			dfs(sum+i*tn[d+1],d+1);
			a[d+1]=-1;
		}
	}
	else dfs(sum+x*tn[d+1],d+1);//否则直接继续搜
	
}
void solve(){
	otto=0;
	for(int i=1;i<=8;i++){//处理数据
		cin>>c[i];
		if(isdigit(c[i]))a[9-i]=c[i]-'0';
		else a[9-i]=-1;
	}
	dfs(0,0);
	cout<<otto<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	//cout<<"hhh"<<is_prime(1)<<" "<<is_prime(2);
	for(int i=2;i<=10000;i++){   //线性筛
		if(!vis[i])b[++top]=i,f[i]=1;;
		for(int j=1;j<=top&&i*b[j]<=10000;j++){
			vis[i*b[j]]=1;
			if(i%b[j]==0){vis[i]==1;break;}
		}
		
	}
	//for(int i=1;i<=100;i++)cout<<b[i]<<" ";
	//cout<<"\n---------------------\n";
	while(T--)solve();
	return 0;
}