#include <bits/stdc++.h>
using namespace std;
long long qpow(long long a, long long b, long long p) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % p;
    a = a * a % p;
    b >>= 1;
  }
  return ans;
}
const int maxn = 2e3 + 10;
int a[maxn], b[maxn];
int mod = 998244353;
int f[2][maxn][12], g[2][maxn][12];
inline int add(long long a, long long b) { return (a + b + mod) % mod; }
long long fac[maxn], invfac[maxn], t[maxn];
void init(int n, long long MOD) {
  fac[0] = 1;
  mod = MOD;
  for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
  invfac[n] = qpow(fac[n], mod - 2, mod);
  for (int i = n; i >= 1; i--) invfac[i - 1] = invfac[i] * i % mod;
}
long long C(long long n, long long m) {
  return n >= m ? fac[n] * invfac[n - m] % mod * invfac[m] % mod : 0;
}
long long cal(long long n, long long m) {
  if (!m) return (n == 0);
  return fac[n] * C(n + m - 1, m - 1) % mod;
}
int main() {
  int T;
  init(maxn - 1, mod);
  fac[0] = 1;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    int cnta = 0, cntb = 0;
    for (int i = 1; i <= n; i++) {
      int x;
      scanf("%d", &x);
      if (to_string(x).size() & 1)
        a[++cnta] = x % 11;
      else
        b[++cntb] = x % 11;
    }
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    f[0][0][0] = 1;
    g[0][0][0] = 1;
    for (int i = 1; i <= cnta; i++) {
      int curi = i & 1, lasti = !(i & 1);
      for (int j = 0; j <= i; j++) {
        for (int k = 0; k <= 10; k++) {
          f[curi][j][k] = add(f[curi][j][k], f[lasti][j][(k - a[i] + 11) % 11]);
          if (j)
            f[curi][j][k] =
                add(f[curi][j][k], f[lasti][j - 1][(k + a[i]) % 11]);
        }
      }
      memset(f[lasti], 0, sizeof(f[lasti]));
    }
    for (int i = 1; i <= cntb; i++) {
      int curi = i & 1, lasti = !(i & 1);
      for (int j = 0; j <= i; j++) {
        for (int k = 0; k <= 10; k++) {
          g[curi][j][k] = add(g[curi][j][k], g[lasti][j][(k - b[i] + 11) % 11]);
          if (j)
            g[curi][j][k] =
                add(g[curi][j][k], g[lasti][j - 1][(k + b[i]) % 11]);
        }
      }
      memset(g[lasti], 0, sizeof(g[lasti]));
    }
    long long ans = 0;
    long long temp = fac[cnta / 2] * fac[cnta - cnta / 2] % mod;
    int m = cnta / 2 + 1;
    for (int i = 0; i <= cntb; i++) {
      for (int j = 0; j < 11; j++) {
        int p = cntb - i;
        long long val = (long long)g[cntb & 1][i][j] *
                        f[cnta & 1][cnta / 2][(11 - j) % 11] % mod * temp %
                        mod * cal(p, m) % mod * cal(i, cnta - cnta / 2) % mod;
        ans = (ans + val) % mod;
      }
    }
    printf("%lld\n", ans);
  }
}
