#include <bits/stdc++.h>
using namespace std;
const long long maxn = 2e3 + 1, mod = 998244353;
long long n, a[maxn], tz, tf, q, T;
long long dpf[2][maxn][11], dpz[2][maxn][11], fac[maxn], ans;
vector<long long> fard, zoj;
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  fac[0] = 1;
  for (long long i = 1; i < maxn; i++) {
    fac[i] = (fac[i - 1] * i) % mod;
  }
  cin >> T;
  while (T--) {
    cin >> n;
    fard.clear();
    zoj.clear();
    q = 0;
    ans = 0;
    fard.push_back(-1);
    zoj.push_back(-1);
    for (long long i = 1; i <= n; i++) {
      cin >> a[i];
      long long ted = 0;
      long long w = 0;
      while (a[i] > 0) {
        ted++;
        if (ted % 2 == 1) {
          w += a[i] % 10;
        } else {
          w -= a[i] % 10;
        }
        a[i] /= 10;
      }
      w = (w % 11 + 11) % 11;
      if (ted % 2 == 0) {
        zoj.push_back(w);
        q += w;
      } else {
        fard.push_back(w);
      }
    }
    tz = zoj.size() - 1;
    tf = fard.size() - 1;
    for (long long i = 1; i < 11; i++) {
      dpf[0][0][i] = 0;
    }
    dpf[0][0][0] = 1;
    for (long long i = 1; i <= tf; i++) {
      for (long long j = 0; j <= i; j++) {
        for (long long k = 0; k < 11; k++) {
          if (i == j) {
            dpf[i % 2][j][k] =
                dpf[(i - 1) % 2][j - 1][((k - fard[i] + 11) % 11)];
          } else if (j == 0) {
            dpf[i % 2][j][k] = dpf[(i - 1) % 2][j][((k + fard[i] + 11) % 11)];
          } else {
            dpf[i % 2][j][k] =
                (dpf[(i - 1) % 2][j - 1][((k - fard[i] + 11) % 11)] +
                 dpf[(i - 1) % 2][j][((k + fard[i] + 11) % 11)]) %
                mod;
          }
        }
      }
    }
    for (long long i = 0; i < 11; i++) {
      dpz[0][0][i] = dpf[tf % 2][(tf + 1) / 2][i] *
                     (fac[tf / 2] * fac[(tf + 1) / 2] % mod) % mod;
    }
    if (tf == 0) {
      if ((q % 11 + 11) % 11 == 0) {
        cout << fac[n] << endl;
        continue;
      } else {
        cout << 0 << endl;
        continue;
      }
    }
    for (long long i = 1; i <= tz; i++) {
      for (long long j = 0; j <= i; j++) {
        for (long long k = 0; k < 11; k++) {
          if (i == j) {
            dpz[i % 2][j][k] =
                (dpz[(i - 1) % 2][j - 1][(k - zoj[i] + 11) % 11] *
                 ((tf / 2) + 1 + j - 1)) %
                mod;
          } else if (j == 0) {
            dpz[i % 2][j][k] = (dpz[(i - 1) % 2][j][(k + zoj[i] + 11) % 11] *
                                (((tf + 1) / 2) + ((i - 1) - j))) %
                               mod;
          } else {
            long long e1 = (dpz[(i - 1) % 2][j - 1][(k - zoj[i] + 11) % 11] *
                            ((tf / 2) + 1 + j - 1)) %
                           mod;
            long long e2 = (dpz[(i - 1) % 2][j][(k + zoj[i] + 11) % 11] *
                            (((tf + 1) / 2) + ((i - 1) - j))) %
                           mod;
            dpz[(i % 2)][j][k] = (e1 + e2) % mod;
          }
        }
      }
    }
    for (long long i = 0; i <= tz; i++) {
      ans = (ans + dpz[tz % 2][i][0]) % mod;
    }
    cout << ans << endl;
  }
  return 0;
}
