#include<bits/stdc++.h>
using namespace std;
char c;
string s;
int T,a,ten[8]={10000000,1000000,100000,10000,1000,100,10,1},dat[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
vector<int> need;

bool if_prime1(int x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			return false;
		}
	}return true;
}

bool if_prime(int x){
	return ((if_prime1(x))&&(if_prime1(x%10000))&&(if_prime1(x%100)));
}

bool if_right(int x){
	int year=x/10000;
	int month=(x%10000)/100;
	int date=x%100;
	if(month<=12){
		if(month==2&&year%4==0){
			if(date>0&&date<=29){
				return true;
			}else{
				return false;
			}
		}else{
			if(date>0&&date<=dat[month]){
				return true;
			}else{
				return false;
			}
		}
	}else{
		return false;
	}
}

int dfs(int x,int th){
	int ret=0;
	a+=th*ten[need[x]];
	if(x==need.size()-1){
		if(if_prime(a)&&if_right(a)){
			//cout<<a<<'\n';
			a-=th*ten[need[x]];
			return 1;
		}else{
			a-=th*ten[need[x]];
			return 0;
		}
	}
	for(int i=0;i<=9;i++){
		ret+=dfs(x+1,i);
	}
	a-=th*ten[need[x]];
	return ret;
}

signed main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>s;
		for(int i=0;i<8;i++){
			c=s[i];
			if(c>='0'&&c<='9'){	
				a=a*10+(c-'0');
			}else{
				a=a*10;
				need.push_back(i);
			}
		}
		if(need.size()==0){
			cout<<"0\n";
			continue;
		}
		cout<<dfs(0,0)+dfs(0,1)+dfs(0,2)+dfs(0,3)+dfs(0,4)+dfs(0,5)+dfs(0,6)+dfs(0,7)+dfs(0,8)+dfs(0,9)<<'\n';
		a=0;
		need.clear();
	}
}