#include <bits/stdc++.h>
using namespace std;
#define maxn 1000000
int prime[maxn]= {0};
void getprime()
{
    prime[1]=1;
    for(int i=2; i<maxn; i++)
    {
        if(prime[i]==0)
        {
            prime[0]++;
            prime[prime[0]]=i;
            for(int j=2; i*j<maxn; j++)
                prime[i*j]=1;
        }
    }
}
int main()
{
    int n;
    string s;
    getprime();
    while(cin>>n)
    {
        for(int i=0; i<n; i++)
        {
            cin>>s;
            int num=0;
            for(int j=0; j<s.l...