#1数据点

#include<bits/stdc++.h>
using namespace std;
int n;
char ch[200];
int main()
{
	cin>>n;
	while(n--)
	{
		cin>>ch;
		cout<<0<<endl;
	}
}

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int prime[99991230+1],cnt,n,num[10],sum;
int isprime[99991230+1];
char ch[10];
int ge()
{
	int ans=0;
	for(int i=1;i<=8;i++)
	ans=ans*10+num[i];
	if(isprime[ans])return 0;
	if(isprime[num[7]*10+num[8]])return 0;
	ans=0;
	for(int i=5;i<=8;i++)
	ans=ans*10+num[i];
	if(isprime[ans])return 0;
	return 1;
}
void dfs(int i){
if(i==8&&num[8]!=-1){if(ge())sum++;return;}
if(i==8&&num[8]==-1)
	{
		if(num[7]==0)for(int j=1;j<=9;j++)
		{
			num[8]=j;if(ge())sum++;
		}
		else for(int j=0;j<=9;j++)
		{
			num[8]=j;
			if(ge())sum++;
		}
		num[8]=-1;
	}
	int flg=0;
	for(int j=i;j<=8;j++)if(num[j]==-1){i=j;flg=1;break;}	
	if(!flg)dfs(8);
	if(i<=2&&num[i]==-1)
	{
		for(int j=0;j<=9;j++)
		{
			num[i]=j;
			dfs(i+1);
		}
		num[i]=-1;
	}
	if(i==3&&num[i]==-1)
	{
		if(num[4]==0)for(int j=1;j<=9;j++)
		{
			num[3]=j;
			dfs(4);
		}
		else for(int j=0;j<=9;j++)
		{
			num[3]=j;
			dfs(4);
		}
		num[i]=-1;
	}
	if(i==4&&num[i]==-1)
	{
		if(num[1]+num[2]+num[3]==0)
			for(int j=1;j<=9;j++)
		{
			num[4]=j;
			dfs(5);
		}
		else for(int j=0;j<=9;j++)
		{
			num[4]=j;
			dfs(5);
		}
		num[4]=-1;
	}
	if(i==5&&num[i]==-1)
	{
		if(num[6]>=3){num[5]=0;dfs(6);}
		else for(int j=0;j<=1;j++)
		{
			num[5]=j;
			dfs(6);
		}
		num[5]=-1;
	}
	if(i==6&&num[i]==-1)
	{
		if(num[5]==1)for(int j=0;j<=2;j++)
		{
			num[6]=j;
			dfs(7);
		}
		else for(int j=1;j<=9;j++)
		{
			num[6]=j;
			dfs(7);
		}
		num[6]=-1;
	}
	if(i==7&&num[i]==-1){
		for(int j=0;j<=2;j++)
		{
			num[7]=j;
			dfs(8);
			
		}num[7]=-1;
	}
	if(i==8&&num[8]==-1)
	{
		if(num[7]==0)for(int j=1;j<=9;j++)
		{
			num[8]=j;if(ge())sum++;
		}
		else for(int j=0;j<=9;j++)
		{
			num[8]=j;
			if(ge())sum++;
		}
		num[8]=-1;
	}
}
int main()
{
    isprime[1]=1;
    for(int i=2;i<=99991230;i++)
    {
        if(!isprime[i])prime[++cnt]=i;
         for(int j=1;j<=cnt&&i*prime[j]<=99991230;j++)
         {
            isprime[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
    cin>>n;
    for(int k=1;k<=n;k++)
    {
    	cin>>ch;
    	int len=strlen(ch);
    	int ce=0;
    	for(int i=1;i<=len;i++)
    	{
    		if(ch[i-1]=='-')num[i]=-1,ce++;
    		else num[i]=ch[i-1]-'0';
		}
		if(ce==0){
			cout<<0<<endl;continue;
		}
		if(num[1]!=-1&&num[2]!=-1&&num[3]!=-1&&num[4]!=-1&&num[1]+num[2]+num[3]+num[4]==0){
			cout<<0<<endl;continue;
		}
		if(num[5]!=-1&&num[6]!=-1&&(((num[5]*10+num[6])>12)||((num[5]*10+num[6])==0))){
			cout<<0<<endl;continue;
		}
		if(num[7]!=-1&&num[8]!=-1&&(((num[7]*10+num[8])>30)||((num[7]*10+num[8])==0))){
			cout<<0<<endl;continue;
		}
		dfs(0);
		cout<<sum<<endl;
		sum=0;
	}
}