#include <bits/stdc++.h>
using namespace std;
int T, n, a[2333], cnt[2], t, l, x, fl, ans, zw, fw;
vector<int> v[2];
int f[2][11][2333], g[2][11][2333], jc[2333];
int S(int x) { return (x + 121) % 11; }
void R(int &x, int y) {
  x += y;
  if (x >= 998244353) x -= 998244353;
}
void doit(vector<int> t) {
  memset(f, 0, sizeof f);
  int sz = t.size(), cur = 0, now = 1;
  f[0][0][0] = 1;
  for (int i = 0; i < sz; i++) {
    memset(f[now], 0, sizeof f[now]);
    for (int j = 0; j <= i; j++) {
      for (int k = 0; k < 11; k++) {
        R(f[now][S(k + t[i])][j + 1], f[cur][k][j]);
        R(f[now][S(k - t[i])][j], f[cur][k][j]);
      }
    }
    swap(f[0], f[1]);
  }
}
int K(long long x, int y) {
  long long t = 1;
  for (y = max(y, 0); y; y >>= 1, x = x * x % 998244353)
    if (y & 1) t = t * x % 998244353;
  return t;
}
int C(int x, int y) {
  if (y <= 0) return 1;
  return (long long)jc[x] * K(jc[x - y], 998244353 - 2) % 998244353 *
         K(jc[y], 998244353 - 2) % 998244353;
}
int done(int zz, int ff) {
  if (ff && !fw) return 0;
  return (long long)jc[zz] * C(zz + zw - 1, zw - 1) % 998244353 * jc[ff] %
         998244353 * C(ff + fw - 1, fw - 1) % 998244353;
}
int main() {
  jc[0] = 1;
  for (int i = 1; i < 2333; i++) {
    jc[i] = (long long)jc[i - 1] * i % 998244353;
  }
  for (cin >> T; T--; ans = 0) {
    cin >> n;
    cnt[0] = cnt[1] = 0;
    v[0].clear();
    v[1].clear();
    for (int i = 1; i <= n; i++) {
      cin >> x;
      for (t = 0, l = 0, fl = 1; x; x /= 10, l ^= 1, fl *= -1) t += x % 10 * fl;
      cnt[l]++;
      v[l].push_back(S(t));
    }
    doit(v[1]);
    memcpy(g, f, sizeof g);
    doit(v[0]);
    fw = (cnt[1] + 1) / 2;
    zw = cnt[1] + 1 - fw;
    for (int i = 0, t; i <= cnt[0]; i++) {
      t = done(i, cnt[0] - i);
      for (int j = 0; j < 11; j++) {
        R(ans, (long long)t * f[0][j][i] % 998244353 * g[0][S(11 - j)][fw] %
                   998244353);
      }
    }
    ans = (long long)ans * jc[fw] % 998244353 * jc[cnt[1] - fw] % 998244353;
    cout << ans << endl;
  }
}
