#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
map<int,int>use;
int used[10];
int n,ans,T,tar;
string s;
int a[10];
bool isprime(int x)
{
	if(x<2)return false;
	for(int i=2;i*i<=x;i++)if(x%i==0)return false;
	return true;
}
void dfs(int d,int num)
{
	if(d==tar+1)return;
	if(use[num])return;
	if(isprime(num)&&!use[num])
	{ans++;/*cout<<"num="<<num<<endl*/;}	
	use[num]=1;
	for(int i=0;i<n;i++)
		if(used[a[i]]>0)
		{used[a[i]]--;dfs(d+1,num*10+a[i]);used[a[i]]++;}
}
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>s;
		n=s.length();
		memset(used,0,sizeof(used));
		ans=0;
		use.clear();
		for(int i=0;i<s.length();i++)
		{a[i]=s[i]-‘0‘;used[s[i]-‘0‘]++;}
		for(int i=n;i>=1;i--)
		{
			tar=i;
			dfs(0,0);
			if(ans==0)break;
		}
		cout<<ans<<endl;
	}
	return 0;
}