#include <bits/stdc++.h>
using namespace std;

int t;
string s[11];
string path="00000000";  //记录当前枚举结果
int ans = 0;

//普通质数筛
bool isPrame(int n) {
	if (n < 2) return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) return false;
	}
	return true;
}

//字符串转整数
int strtoint(string s1) {
	int num = 0;
	for (int i = 0; i < s1.size(); i++) {
		num = num * 10 + (s1[i] - '0');
	}
	return num;
}

//判断年月日合法
bool isRightmonthyear(int year, int month, int days) {
	int m[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
	if (month == 2) {  //如果是2月
		if (year % 400 == 0 || (year % 100 != 0 && year % 4 == 0)) {  //如果是闰年
			return days <= m[month] + 1;  //是不是在29之内
		} else {
			return days <= m[month];
		}
	} else {
		return days <= m[month];  //如果不是2月，是否在合法范围内
	}
} 	

//判断现枚举结果是否正确
bool isok(string &s1) {
	string year = s1.substr(0,4);  //这三行得年月日
	string month = s1.substr(4,2); 
	string days = s1.substr(6,2);
	if (!isRightmonthyear(strtoint(year), strtoint(month), strtoint(days))) return false;  //日期不合法就不对
	year += month + days; 
	month += days;
	if (isPrame(strtoint(year))) return true; //判断年月日是不是质数
	else return false;
}

//搜索本体,i位置从最后一名开始枚举
void f(string &s1, int i) {
	if (i == 5) {  //如果i到5位置，日已经枚举完了
		int days = strtoint(path.substr(6,2));  //得到日期
		if (days > 31 || days < 2 || !isPrame(days)) return; //先判断日期是否正确，不正确后面就不搜了
	}
	if (i == 3) {  //如果i到3位置，月和日已经枚举完了
		int month = strtoint(path.substr(4,2)); //先看月份
		if (month > 12 || month < 1) return;  //月份不对，后面就不搜了
		month = strtoint(path.substr(4,4));  //再看月+日
		if (!isPrame(month)) return;  //不是质数就不搜了
	}
	if (i < 0) {  //到越界位，所有位置都已经枚举完了
		if (isok(path)) {  //看到年+月+日结果合法
			ans++;  //合法就计数
		}
		return;
	}	
	if (s1[i] != '-') {  //如果当前位是数字
		path[i] = s1[i];  //正常记录
		f(s1, i - 1);  //向左边枚举
	}
	else {
		int flag = 9;  //如果是-，看当前位置是啥位置，确定枚举范围
		if (i <= 3) {  //i小于等于3的话，年份位置都从0-9枚举
			flag = 9;
		} else if (i == 4) {  //i是4的话，月份第一个位，只能枚举0-1
			flag = 1;
		} else if (i == 5) {  //i是5的话，月份第二个位，枚举0-9
			flag = 9;
		} else if (i == 6) {  //i是6的话，日的第一位，枚举0-3
			flag = 3;
		} else {
			flag = 9;   //其它都是枚举0-9
		}
		for (int k = 0; k <= flag; k++) {
			path[i] = char(k + '0');  //枚举结果放进路径中
			f(s1, i - 1);  //向左继续
		}
	}
}

int main() {
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> s[i];
		f(s[i],7);  //从最后一位开始搜
		cout << ans << '\n';  //输出答案
		ans = 0;  //答案清零
	}	
	
	return 0;
}

一开始我是从0位置正向去搜，70分，3个TLE，后面想着应先从日期开始判断，所以改成了从右往左去搜索，加了一部分剪枝的逻辑，反而变成0分。没找到具体问题在哪。因此求助各位大佬。