#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5, MOD = 998244353;
int a[N], n, dp[2][N][12][2], fac[N];
vector<int> Odd, Even;
long long mod_Pow(long long a, long long n, long long m) {
  a %= m;
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return res;
}
int inv(int a) { return mod_Pow(a, MOD - 2, MOD); }
int C(int k, int n) {
  if (k > n) return 0;
  return (1LL * fac[n] * inv((1LL * fac[k] * fac[n - k]) % MOD)) % MOD;
}
void mul(int &a, int b) { a = (1LL * a * b) % MOD; }
void solve() {
  cin >> n;
  Odd.clear();
  Even.clear();
  Odd.push_back(0);
  Even.push_back(0);
  int evenSum = 0;
  for (int i = (1), _b = (n); i <= _b; i++) {
    cin >> a[i];
    int tmp = a[i], digitSum = 0, sign = 1;
    stack<int> digit;
    while (!digit.empty()) digit.pop();
    while (tmp) {
      digit.push(tmp % 10);
      tmp /= 10;
    }
    while (!digit.empty()) {
      int cur = digit.top();
      digit.pop();
      digitSum += sign * cur;
      sign *= -1;
    }
    if (int(log10(a[i])) % 2 != 0) {
      Even.push_back(digitSum);
    } else
      Odd.push_back(digitSum);
  }
  int nn = Odd.size() - 1;
  memset(dp, 0, sizeof dp);
  dp[0][0][0][0] = dp[0][0][0][1] = 1;
  for (int id = (1), _b = (nn); id <= _b; id++) {
    int i = id & 1;
    for (int j = (0), _b = (id); j <= _b; j++)
      for (int k = 0, _n = (11); k < _n; k++) {
        int posRem = k - (Odd[id] % 11) + 11;
        posRem %= 11;
        int negRem = k + (Odd[id] % 11) + 11;
        negRem %= 11;
        if (j >= 1) dp[i][j][k][0] = max(0, dp[i ^ 1][j - 1][posRem][0]);
        (dp[i][j][k][0] += dp[i ^ 1][j][negRem][0]) %= MOD;
      }
    for (int j = 0, _n = (N); j < _n; j++)
      for (int k = 0, _n = (11); k < _n; k++) dp[i ^ 1][j][k][0] = 0;
  }
  for (int id = (1), _b = (n - nn); id <= _b; id++) {
    int i = id & 1;
    for (int j = (0), _b = (id); j <= _b; j++)
      for (int k = 0, _n = (11); k < _n; k++) {
        int posRem = k - (Even[id] % 11) + 11;
        posRem %= 11;
        int negRem = k + (Even[id] % 11) + 11;
        negRem %= 11;
        if (j >= 1) dp[i][j][k][1] = max(0, dp[i ^ 1][j - 1][posRem][1]);
        (dp[i][j][k][1] += dp[i ^ 1][j][negRem][1]) %= MOD;
      }
    for (int j = 0, _n = (N); j < _n; j++)
      for (int k = 0, _n = (11); k < _n; k++) dp[i ^ 1][j][k][1] = 0;
  }
  int res = 0;
  int laste = (n - nn) & 1;
  int lasto = (nn)&1;
  if (nn == 0) {
    int res = dp[laste][n][0][1];
    mul(res, fac[n]);
    cout << res << '\n';
    return;
  }
  for (int rem = 0, _n = (11); rem < _n; rem++) {
    int erem = (-rem + 11) % 11;
    int cur = dp[lasto][nn / 2 + (nn % 2 != 0)][rem][0];
    int tmp = 0;
    for (int i = (0), _b = (n - nn); i <= _b; i++) {
      int cnt = dp[laste][i][erem][1];
      mul(cnt, fac[i]);
      mul(cnt, fac[n - nn - i]);
      mul(cnt, C(i, i + (nn + 1) / 2 + (nn % 2 == 0) - 1));
      mul(cnt, C(n - nn - i, n - nn - i + (nn + 1) / 2 - 1));
      tmp += cnt;
      tmp %= MOD;
    }
    if (n - nn == 0 && rem == 0) tmp = 1;
    mul(tmp, cur);
    mul(tmp, fac[nn / 2 + (nn % 2 != 0)]);
    mul(tmp, fac[nn / 2]);
    res += tmp;
    res %= MOD;
  }
  cout << res << '\n';
}
int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  clock_t tStart = clock();
  fac[0] = 1;
  for (int i = (1), _b = (N - 5); i <= _b; i++)
    fac[i] = (1LL * fac[i - 1] * i) % MOD;
  int tc;
  cin >> tc;
  for (int nhi = 0, _n = (tc); nhi < _n; nhi++) {
    solve();
  }
  fprintf(stderr, "Time taken: %.2fs\n",
          (double)(clock() - tStart) / CLOCKS_PER_SEC);
  return 0;
}
