#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-9;
template <typename T>
inline void read(T& x) {
  char c;
  bool nega = 0;
  while ((!isdigit(c = getchar())) && c != '-')
    ;
  if (c == '-') {
    c = getchar();
    nega = 1;
  }
  x = c - 48;
  while (isdigit(c = getchar())) {
    x = x * 10 + c - 48;
  }
  if (nega) x = -x;
}
template <typename T>
void Write(T x) {
  if (x > 9) Write(x / 10);
  putchar(x % 10 + 48);
}
template <typename T>
void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  Write(x);
  putchar(' ');
}
template <typename T>
void writeln(T x) {
  write(x);
  putchar('\n');
}
const int base = 998244353;
const int N = 2003;
int n;
int a[N];
int sz[N];
int Pow10[10];
long long fac[2 * N];
bool odd, even;
int sizeOfNum(int n) {
  int res = 0;
  while (n) {
    res++;
    n /= 10;
  }
  return res;
}
void init() {
  Pow10[0] = 1;
  fac[0] = 1;
  for (int i = 1; i <= 9; i++) Pow10[i] = Pow10[i - 1] * 10;
  for (int i = 1; i < 2 * N; i++) {
    fac[i] = (fac[i - 1] * i) % base;
  }
}
void input() {
  read(n);
  int s = 0;
  odd = 0, even = 0;
  for (int i = 1; i <= n; i++) {
    read(a[i]);
    sz[i] = sizeOfNum(a[i]);
    if (sz[i] % 2)
      odd = 1;
    else
      even = 1;
  }
}
bool used[11];
int res = 0;
void Try(int i, int mod) {
  if (i == n + 1 && mod == 0) {
    res++;
    return;
  }
  for (int j = 1; j <= n; j++)
    if (!used[j]) {
      used[j] = 1;
      int new_mod = (1LL * mod * Pow10[sz[j]] + a[j]) % 11;
      Try(i + 1, new_mod);
      used[j] = 0;
    }
}
void sub1() {
  res = 0;
  Try(1, 0);
  writeln(res);
}
vector<int> num[2];
long long dp[N][11][2];
long long temp[N][11];
int sum[N][2];
void calc(int id) {
  int len = num[id].size();
  dp[0][0][id] = 1;
  for (auto x : num[id]) {
    for (int i = 0; i <= len; i++)
      for (int j = 0; j <= 10; j++) temp[i][j] = 0;
    for (int i = 0; i <= len; i++) {
      for (int j = 0; j <= 10; j++) {
        temp[i][(j + x) % 11] = (temp[i][(j + x) % 11] + dp[i][j][id]) % base;
        temp[i + 1][(j - x + 11) % 11] =
            (temp[i + 1][(j - x + 11) % 11] + dp[i][j][id]) % base;
      }
    }
    for (int i = 0; i <= len; i++)
      for (int j = 0; j <= 10; j++) dp[i][j][id] = temp[i][j];
  }
}
void sub4() {
  num[0].clear();
  num[1].clear();
  for (int i = 1; i <= n; i++) {
    num[sz[i] % 2].push_back(a[i] % 11);
  }
  for (int i = 0; i <= 2000; i++)
    for (int j = 0; j <= 10; j++)
      for (int k = 0; k <= 1; k++) dp[i][j][k] = 0;
  calc(0);
  calc(1);
  int len1 = num[1].size() / 2;
  int len2 = num[1].size() - len1;
  long long res = 0;
  for (int i = 0; i <= 10; i++)
    for (int j = 0; j <= num[0].size(); j++) {
      long long tmp = (dp[len1][i][1] * dp[j][(11 - i) % 11][0]) % base;
      int d1 = j, d0 = num[0].size() - j;
      long long v0 = fac[len2 + d0];
      if (len1 != len2) v0 = (fac[len2 + d0 - 1] * len2) % base;
      long long v1 = fac[len1 + d1];
      if (len1 == len2) v1 = (fac[len1 + d1 - 1] * len1) % base;
      tmp = (tmp * v0) % base;
      tmp = (tmp * v1) % base;
      res = (res + tmp);
      if (res >= base) res -= base;
    }
  writeln(res);
}
void solve() {
  if (n <= 9) {
    sub1();
    return;
  }
  if (even && !odd) {
    cerr << "even"
         << " = " << even << '\n';
    ;
    int cur = 0;
    for (int i = 1; i <= n; i++) {
      int tmp = a[i];
      int flag = 0;
      while (tmp) {
        if (flag)
          cur += tmp % 10;
        else
          cur -= tmp % 10;
        tmp /= 10;
        flag = 1 - flag;
      }
    }
    if (cur == 0)
      writeln(fac[n]);
    else
      writeln(0);
    return;
  }
  sub4();
}
int main() {
  init();
  int test;
  read(test);
  while (test--) {
    input();
    solve();
  }
  return 0;
}
