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

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair
#define pb push_back

#define scan(x) do{Mi=1;while((x=getchar())<'0'){if (x=='-') Mi=-1;} for(x-='0'; '0'<=(L=getchar()); x=(x<<3)+(x<<1)+L-'0'); x*=Mi;}while(0)
char L;
int Mi;

const int MAXN = 32000;
const int MAGIJA = 1002;
const int MAXM = 1000000;

vector <int> imam[MAXM], input;
int bitan[MAXM];

int ans[MAXN];


inline void spremi(int x) {
  int niz[10];
  memset(niz, 0, sizeof niz);
  int pomoc;
  for(int i = 0; i < 10; i++) {
    if(x) {
      pomoc = x / 10;
      niz[x - pomoc * 10]++, x = pomoc;
    }
    else
      break;
  }

  ll broj = 0;
  REP(j, niz[9]) broj *= 10, broj += 9;
  REP(j, niz[8]) broj *= 10, broj += 8;
  REP(j, niz[7]) broj *= 10, broj += 7;
  REP(j, niz[6]) broj *= 10, broj += 6;
  REP(j, niz[5]) broj *= 10, broj += 5;
  REP(j, niz[4]) broj *= 10, broj += 4;
  REP(j, niz[3]) broj *= 10, broj += 3;
  REP(j, niz[2]) broj *= 10, broj += 2;
  REP(j, niz[1]) broj *= 10, broj += 1;
  REP(j, niz[0]) broj *= 10;

  if (bitan[broj / MAGIJA]) imam[broj / MAGIJA].pb(broj);
}

/// Set your CPU's L1 data cache size (in bytes) here
const int64_t L1D_CACHE_SIZE = 32768;

/// Generate primes using the segmented sieve of Eratosthenes.
/// This algorithm uses O(n log log n) operations and O(sqrt(n)) space.
/// @param limit  Sieve primes <= limit.
///
void segmented_sieve(int64_t limit)
{
  int64_t sqrt = (int64_t) std::sqrt(limit);
  int64_t segment_size = std::max(sqrt, L1D_CACHE_SIZE);
  //int64_t count = (limit < 2) ? 0 : 1;

  // we sieve primes >= 3
  int64_t i = 3;
  int64_t n = 3;
  int64_t s = 3;

  std::vector<char> sieve(segment_size);
  std::vector<char> is_prime(sqrt + 1, true);
  std::vector<int64_t> primes;
  std::vector<int64_t> multiples;

  for (int64_t low = 0; low <= limit; low += segment_size)
  {
    std::fill(sieve.begin(), sieve.end(), true);

    // current segment = [low, high]
    int64_t high = low + segment_size - 1;
    high = std::min(high, limit);

    // generate sieving primes using simple sieve of Eratosthenes
    for (; i * i <= high; i += 2)
      if (is_prime[i])
        for (int64_t j = i * i; j <= sqrt; j += i)
          is_prime[j] = false;

    // initialize sieving primes for segmented sieve
    for (; s * s <= high; s += 2)
    {
      if (is_prime[s])
      {
           primes.push_back(s);
        multiples.push_back(s * s - low);
      }
    }

    // sieve the current segment
    for (std::size_t i = 0; i < primes.size(); i++)
    {
      int64_t j = multiples[i];
      for (int64_t k = primes[i] * 2; j < segment_size; j += k)
        sieve[j] = false;
      multiples[i] = j - segment_size;
    }

    for (; n <= high; n += 2)
      if (sieve[n - low]) // n is a prime
        spremi(n);
  }

}


void solve() {
  int n, x;
  vector <int> a;
  scan(n);
  int niz[10];
  memset(niz, 0, sizeof niz);
  REP(i, n) {
    scan(x);
    niz[x]++;
  }
  ll broj = 0;
  for (int i = 9; i >= 0; i--) {
    REP(j, niz[i]) {
      broj *= 10;
      broj += i;
    }
  }
  input.pb(broj);
  bitan[broj / MAGIJA] = 1;
}


int main() {
  int t;
  scan(t);
  REP(i, t) solve();
  segmented_sieve(1000000000);
  spremi(2);
  REP(i, t) {
    int cnt = 0;
    for (auto &x : imam[input[i] / MAGIJA]) cnt += (x == input[i]);
    printf("%d\n",cnt);
  }
}