#include <bits/stdc++.h>
using namespace std;
int read() {
  int v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
const int N = 2050;
const long long MOD = 998244353, r2 = (MOD + 1) / 2;
long long f[2][N][11], g[2][N][11], de[N][N], cur[N << 1], h[N >> 1][N << 1],
    fac[N << 1], t1[N << 1], t2[N << 1], C[N][N];
pair<int, int> a[N];
int b[N], c[N];
int n;
long long pw(long long a, long long b) {
  long long re = 1;
  while (b) {
    if (b & 1) re = re * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return re;
}
long long query(int i, int j) {
  if (i == 0 && j == 0) return 1;
  return C[i + j - 1][j] * fac[j] % MOD;
}
int main() {
  fac[0] = 1;
  for (int i = 1; i <= 2040; i++) fac[i] = fac[i - 1] * i % MOD;
  for (int i = 0; i <= 2040; i++) {
    de[i][0] = 1;
    for (int j = 1; j <= i; j++) de[i][j] = de[i][j - 1] * (i - j + 1) % MOD;
  }
  C[0][0] = 1;
  for (int i = 1; i <= 2040; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
  }
  int cas = read();
  while (cas--) {
    n = read();
    for (int i = 1; i <= n; i++) {
      int u = read();
      a[i].first = a[i].second = 0;
      while (u) {
        if (a[i].second)
          a[i].first -= u % 10;
        else
          a[i].first += u % 10;
        a[i].second ^= 1;
        u /= 10;
      }
      a[i].first = (a[i].first % 11 + 11) % 11;
    }
    int n1 = 0, n2 = 0, s1 = 0, s2 = 0;
    for (int i = 1; i <= n; i++)
      if (a[i].second & 1)
        b[++n1] = a[i].first, s1 += a[i].first;
      else
        c[++n2] = a[i].first, s2 += a[i].first;
    s1 %= 11, s2 %= 11;
    for (int i = 0; i <= n1 / 2; i++)
      for (int j = 0; j < 11; j++) f[0][i][j] = 0;
    f[0][0][0] = 1;
    for (int i = 0; i < n1; i++) {
      int now = i & 1, nxt = !now;
      for (int j = 0; j <= n1 / 2; j++)
        for (int k = 0; k < 11; k++) f[nxt][j][k] = 0;
      for (int j = 0; j <= n1 / 2; j++)
        for (int k = 0; k < 11; k++) {
          (f[nxt][j][k] += f[now][j][k]) %= MOD;
          if (j < n1 / 2)
            (f[nxt][j + 1][(k + b[i + 1]) % 11] += f[now][j][k]) %= MOD;
        }
    }
    for (int i = 0; i <= n2; i++)
      for (int j = 0; j < 11; j++) g[0][i][j] = 0;
    g[0][0][0] = 1;
    for (int i = 0; i < n2; i++) {
      int now = i & 1, nxt = !now;
      for (int j = 0; j <= n2; j++)
        for (int k = 0; k < 11; k++) g[nxt][j][k] = 0;
      for (int j = 0; j <= n2; j++)
        for (int k = 0; k < 11; k++) {
          (g[nxt][j][k] += g[now][j][k]) %= MOD;
          if (j < n2)
            (g[nxt][j + 1][(k + c[i + 1]) % 11] += g[now][j][k]) %= MOD;
        }
    }
    long long ans = 0;
    for (int i = 0; i < 11; i++)
      for (int j = 0; j < 11; j++)
        if ((2 * i - s1 + 2 * j - s2) % 11 == 0)
          for (int k = 0; k <= n2; k++)
            (ans += g[n2 & 1][k][j] * query(n1 / 2 + 1, k) % MOD *
                    query((n1 + 1) / 2, n2 - k) % MOD * f[n1 & 1][n1 / 2][i] %
                    MOD * de[n1 / 2][n1 / 2] % MOD *
                    de[(n1 + 1) / 2][(n1 + 1) / 2] % MOD) %= MOD;
    printf("%lld\n", ans);
  }
}
