#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;

}