It is Borya's eleventh birthday, and he has got a great present: n cards with numbers. The i-th card has the number a_{i} written on it. Borya wants to put his cards in a row to get one greater number. For example, if Borya has cards with numbers 1, 31, and 12, and he puts them in a row in this order, he would get a number 13112.

He is only 11, but he already knows that there are n! ways to put his cards in a row. But today is a special day, so he is only interested in such ways that the resulting big number is divisible by eleven. So, the way from the previous paragraph is good, because 13112 = 1192 × 11, but if he puts the cards in the following order: 31, 1, 12, he would get a number 31112, it is not divisible by 11, so this way is not good for Borya. Help Borya to find out how many good ways to put the cards are there.

Borya considers all cards different, even if some of them contain the same number. For example, if Borya has two cards with 1 on it, there are two good ways.

Help Borya, find the number of good ways to put the cards. This number can be large, so output it modulo 998244353.


-----Input-----

Input data contains multiple test cases. The first line of the input data contains an integer t — the number of test cases (1 ≤ t ≤ 100). The descriptions of test cases follow.

Each test is described by two lines.

The first line contains an integer n (1 ≤ n ≤ 2000) — the number of cards in Borya's present.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^9) — numbers written on the cards.

It is guaranteed that the total number of cards in all tests of one input data doesn't exceed 2000.


-----Output-----

For each test case output one line: the number of ways to put the cards to the table so that the resulting big number was divisible by 11, print the number modulo 998244353.


-----Example-----
Input
4
2
1 1
3
1 31 12
3
12345 67 84
9
1 2 3 4 5 6 7 8 9

Output
2
2
2
31680

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'mod = 998244353\nf0 = [ [0 for i in range(11)] for j in range(2010) ]\nf1 = [ [0 for i in range(11)] for j in range(2010) ]\nfac = [0 for i in range(2010)]\ntab = [0 for i in range(11)]\nC = [ [0 for i in range(2010)] for j in range(2010) ]\n\ndef Init() :\n    fac[0] = 1\n    for i in range(2010) :\n        if i > 0 : fac[i] = fac[i - 1] * i % mod\n        C[i][0] = 1\n        for j in range(1, 2010) :\n            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod\n\ndef len(x) :\n    res = 0\n    while x > 0 :\n        res += 1\n        x = x // 10\n    return res\n            \ndef solve() :\n    n = int(input())\n    f0[0][0] = f1[0][0] = 1\n    a = list(map(int, input().split()))\n    c0, c1 = 0, 0\n    s0, s1 = 0, 0\n    for nu in a :\n        m = nu % 11\n        if len(nu) & 1 :\n            c1 += 1\n            s1 += m\n            for i in range(11) :\n                f1[c1][i] = 0\n            for i in range(c1 - 1, -1, -1) :\n                for j in range(11) :\n                    if f1[i][j] == 0 : continue\n                    f1[i + 1][(j + m) % 11] += f1[i][j]\n                    f1[i + 1][(j + m) % 11] %= mod\n        else :\n            c0 += 1\n            s0 += m\n            for i in range(11) :\n                f0[c0][i] = 0\n            for i in range(c0 - 1, -1, -1) :\n                for j in range(11) :\n                    if f0[i][j] == 0 : continue\n                    f0[i + 1][(j + m) % 11] += f0[i][j]\n                    f0[i + 1][(j + m) % 11] %= mod\n    s1 %= 11\n    s0 %= 11\n    part = c1 // 2\n    for i in range(11) :\n        tab[i] = 0\n    for i in range(11) :\n        tab[(i + i + 11 - s1) % 11] = f1[c1 - part][i]\n    for i in range(11) :\n        tab[i] = tab[i] * fac[part] % mod * fac[c1 - part] % mod\n\n    ans = 0\n    if c1 == 0 :\n        ans = f0[c0][0] * fac[c0]\n    elif c0 == 0 :\n        ans = tab[0]\n    else :\n        for i in range(c0 + 1) :\n            for j in range(11) :\n                if f0[i][j] == 0 : continue\n                # print(f0[i][j], tab[(j + j + 11 - s0) % 11] \\\n                # , fac[i] % mod * fac[c0 - i] % mod, C[j + (c1 - part) - 1][(c1 - part) - 1] % mod * C[part + c0 - i][part] % mod )\n                ans = ( ans \\\n                        + fac[i] % mod * fac[c0 - i] % mod \\\n                        * f0[i][j] * tab[(j + j + 11 - s0) % 11] % mod \\\n                        * C[i + (c1 - part) - 1][(c1 - part) - 1] % mod \\\n                        * C[part + c0 - i][part]\n ) % mod\n    print(ans)\n\nInit()\nT = int(input())\nfor ttt in range(T) : solve()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 97939713