#include <bits/stdc++.h>
using namespace std;
int getSign(int x) {
  int f = -1;
  while (x >= 10) {
    f = -f;
    x /= 10;
  }
  return f;
}
const int mod = 998244353, maxn = 2000;
long long fac[maxn + 10], invfac[maxn + 10];
int dp[maxn + 10][maxn + 10][11];
int sign[maxn + 10], a[maxn + 10], sp[maxn + 10], no[maxn + 10];
long long temp[11];
long long split(int n, int r) {
  return fac[n + r - 1] * invfac[n] % mod * invfac[r - 1] % mod;
}
long long qp(long long x, long long y) {
  if (y == 0) return 1;
  if (y == 1) return x;
  long long ret = qp(x, y >> 1);
  ret = ret * ret % mod;
  if ((y & 1) == 1) ret = ret * x % mod;
  return ret;
}
int main() {
  int T;
  cin >> T;
  memset(dp, 0, sizeof dp);
  fac[0] = 1;
  for (int i = 1; i <= maxn; i++) fac[i] = fac[i - 1] * i % mod;
  invfac[maxn] = qp(fac[maxn], mod - 2);
  for (int i = maxn - 1; i >= 0; i--) invfac[i] = invfac[i + 1] * (i + 1) % mod;
  while (T--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
      sign[i] = getSign(a[i]);
      a[i] %= 11;
      if (sign[i] < 0)
        sp[++cnt] = a[i];
      else
        no[i - cnt] = a[i];
    }
    if (cnt == 0) {
      int res = 0;
      for (int i = 1; i <= n; i++) res = (res + a[i]) % 11;
      long long ans = 1;
      for (int i = 2; i <= n; i++) ans = ans * i % mod;
      if (res == 0)
        cout << ans << '\n';
      else
        cout << "0\n";
      continue;
    }
    int cntz = (cnt / 2) + (cnt % 2), cntf = cnt / 2,
        cntz2 = ((cnt + 1) / 2) + ((cnt + 1) % 2), cntf2 = (cnt + 1) / 2;
    dp[0][0][0] = 1;
    for (int i = 0; i <= cntz; i++)
      for (int j = 0; j <= cntf; j++)
        if (i + j > 0)
          for (int k = 0; k < 11; k++) {
            dp[i][j][k] = 0;
            if (i > 0)
              dp[i][j][k] =
                  (dp[i][j][k] + dp[i - 1][j][(k + 11 - sp[i + j]) % 11]) % mod;
            if (j > 0)
              dp[i][j][k] =
                  (dp[i][j][k] + dp[i][j - 1][(k + sp[i + j]) % 11]) % mod;
          }
    for (int k = 0; k < 11; k++) temp[k] = dp[cntz][cntf][k];
    dp[0][0][0] = 1;
    for (int i = 0; i <= n - cnt; i++)
      for (int j = 0; j <= n - cnt - i; j++)
        if (i + j > 0)
          for (int k = 0; k < 11; k++) {
            dp[i][j][k] = 0;
            if (i > 0)
              dp[i][j][k] =
                  (dp[i][j][k] + dp[i - 1][j][(k + 11 - no[i + j]) % 11]) % mod;
            if (j > 0)
              dp[i][j][k] =
                  (dp[i][j][k] + dp[i][j - 1][(k + no[i + j]) % 11]) % mod;
          }
    long long ans = 0;
    for (int k = 0; k < 11; k++)
      for (int i = 0; i <= n - cnt; i++)
        ans =
            (ans + temp[k] * dp[i][n - cnt - i][(11 - k) % 11] % mod * fac[i] %
                       mod * split(i, cntz2) % mod * fac[n - cnt - i] % mod *
                       split(n - cnt - i, cntf2) % mod) %
            mod;
    cout << ans * fac[cntz] % mod * fac[cntf] % mod << '\n';
  }
  return 0;
}
