CF856C.Eleventh Birthday

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.

今天是鲍里亚的十一岁生日，他收到了一份很棒的礼物：$n$ 张写有数字的卡片。第 $i$ 张卡片上写的数字为 $a_i$。鲍里亚想把这些卡片排成一排，从而拼成一个大整数。例如，若鲍里亚有数字分别为 $1$、$31$ 和 $12$ 的三张卡片，并按此顺序排成一排，则得到的数为 $13112$。

他虽只有 11 岁，却已经知道共有 $n!$ 种不同的排列方式。但今天是特殊的日子，因此他只关心那些能使最终拼成的大整数能被 $11$ 整除的排列方式。例如，前一段中的排列方式是可行的，因为 $13112 = 1192 \times 11$；但如果他按如下顺序排列卡片：$31$、$1$、$12$，则得到的数为 $31112$，它不能被 $11$ 整除，因此这种排列方式对鲍里亚来说不可行。请帮助鲍里亚计算出有多少种可行的排列方式。

鲍里亚认为所有卡片都是互不相同的，即使其中某些卡片上写的数字相同。例如，若鲍里亚有两张写有数字 $1$ 的卡片，则存在两种可行的排列方式。

请帮助鲍里亚求出可行的排列方式总数。该数可能很大，请将结果对 $998244353$ 取模后输出。

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 ≤ 109) — 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.

输入数据包含多个测试用例。输入数据的第一行包含一个整数 $t$ —— 测试用例的数量（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例由两行描述。

第一行包含一个整数 $n$（$1 \le n \le 2000$）—— Borya 收到的卡片数量。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）—— 卡片上所写的数字。

保证单组输入数据中所有测试用例的卡片总数不超过 $2000$。

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.

对于每个测试用例，输出一行：将卡片放置在桌面上的方式数目，使得所形成的大型数字能被 11 整除；请输出该数目对 998244353 取模的结果。