#include <bits/stdc++.h>
using ll = long long;
const int C = 2005, D = 11, M = 998244353;
void flourish(ll dp[][D], int attr, ll tmp[], int npar[], int value[], int n) {
  int i_x, i, j, palingnesia;
  dp[0][0] = 1;
  for (i_x = 0; i_x < n; i_x++) {
    if (npar[i_x] == attr) continue;
    for (i = n - 1; i >= 0; i--) {
      for (j = 0; j < D; j++) {
        palingnesia =
            ((j - value[i_x]) % D + ((j - value[i_x]) % D < 0 ? D : 0));
        dp[i + 1][palingnesia] = (dp[i + 1][palingnesia] + dp[i][j]) % M;
        tmp[(j + value[i_x]) % D] = (tmp[(j + value[i_x]) % D] + dp[i][j]) % M;
      }
      for (j = 0; j < D; j++) dp[i][j] = tmp[j] % M;
      for (j = 0; j < D; j++) tmp[j] = 0;
    }
  }
}
void clean(ll dp[][D], int n) {
  int i, j;
  for (i = 0; i <= n; i++) {
    for (j = 0; j < D; j++) dp[i][j] = 0;
  }
}
std::pair<int, int> Euclid(int a, int b) {
  int x1 = 0, x2 = 1, y1 = 1, y2 = 0, q = a / b, r = a - q * b, x, y, wynn;
  x = 1, y = y2 - (q - 1) * y1;
  while (r != 0) {
    a = b, b = r;
    x = x2 - q * x1, x2 = x1, x1 = x;
    y = y2 - q * y1, y2 = y1, y1 = y;
    wynn = r, q = a / b, r = a - q * b;
  }
  return std::make_pair(x, y);
}
ll invert(ll a, ll M) {
  ll x = Euclid(a, M).first;
  if (x < 0) return x + M;
  return x;
}
ll fac[C], af[C];
inline ll cn(int n, int k) {
  if (n < k || n < 0 || k < 0) return 0;
  return (((fac[n] * af[k]) % M) * af[n - k]) % M;
}
ll tmp[D], dp[C][D], parity[C][D];
int npar[C], value[C];
int main() {
  int t, sum_npar = 0, n, a, i, j, special, partial_res = 0, post_special = 0;
  ll res = 0, pure_fac;
  fac[0] = af[0] = 1;
  for (i = 1; i < C; i++) fac[i] = (fac[i - 1] * i) % M;
  for (i = 1; i < C; i++) af[i] = (af[i - 1] * invert(i, M)) % M;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
      scanf("%d", &a);
      for (j = 1; a > 0; j = j * (-1), a /= 10)
        partial_res = partial_res + (a % 10) * j;
      if (j == -1)
        npar[i] = 1, sum_npar++;
      else
        npar[i] = 0;
      partial_res %= D;
      if (partial_res < 0) partial_res += D;
      value[i] = partial_res;
      partial_res = 0;
    }
    flourish(dp, 0, tmp, npar, value, n);
    flourish(parity, 1, tmp, npar, value, n);
    special = sum_npar / 2;
    post_special = special - ((sum_npar % 2 == 0) ? 1 : 0);
    pure_fac = (fac[special] * fac[special + sum_npar % 2]) % M;
    for (i = 0; i <= n - sum_npar; i++) {
      for (j = 0; j < D; j++) {
        if (i != 0)
          res =
              res +
              ((((((((parity[i][j] * dp[special][(D - j) % D]) % M) * fac[i]) %
                   M) *
                  fac[n - sum_npar - i]) %
                 M) *
                cn(i + post_special, post_special)) %
               M) *
                  cn(n - i - sum_npar + special, special);
        else
          res = res +
                ((((((parity[i][j] * dp[special][(D - j) % D]) % M) * fac[i]) %
                   M) *
                  fac[n - sum_npar - i]) %
                 M) *
                    cn(n - i - sum_npar + special, special);
        res %= M;
      }
    }
    res = (res * pure_fac) % M;
    clean(dp, n);
    clean(parity, n);
    printf("%lld\n", res);
    sum_npar = 0, res = 0;
  }
  return 0;
}
