知论派的谜题（puzzle）

给定 $k$ 个长度均为 $n$ 的正整数 $a_1,a_2,\ldots,a_k$。

一次列重排指选择一个 $1$ 到 $n$ 的排列 $p_1,p_2,\ldots,p_n$，并同时将每一个数的第 $p_j$ 位放到重排后第 $j$ 位。也就是说，移动的是所有数的同一列，不能单独打乱某一个数。

形式化地，重排后第 $i$ 个数为 $b_i=a_{i,p_1}a_{i,p_2}\cdots a_{i,p_n}$。

请你求有多少个排列 $p$，使得重排后的 $k$ 个数满足 $b_1+b_2+\cdots+b_{k-1}=b_k$，并且所有 $b_i$ 都没有前导零。

答案对 $998244353$ 取模。

如果两列上的数字完全相同，但它们来自原来的不同位置，则交换这两列仍然视为不同的列重排。

样例 1 输入

3
3
12
23
35
3
10
20
30
3
111
222
333

样例 1 输出

2
1
6

样例 1 解释

对于第 $1$ 组测试数据，两种合法列重排分别得到 $12+23=35$ 和 $21+32=53$。

对于第 $2$ 组测试数据，若交换两列会得到 $01,02,03$，出现前导零，因此不合法；只有原顺序合法。

对于第 $3$ 组测试数据，三列完全相同，但列的位置互不相同，因此 $3!$ 种列重排都要计入答案。

样例 2 输入

2
3
1
1
3
4
12
23
34
69

样例 2 输出

0
2

样例 2 解释

对于第 $1$ 组测试数据，只有一列，且 $1+1\ne 3$，因此答案为 $0$。

对于第 $2$ 组测试数据，两种合法列重排分别得到 $12+23+34=69$ 和 $21+32+43=96$。

样例 3

见附加文件中的 puzzle3.in 和 puzzle3.ans。

该样例满足测试点 $1$ 的限制。

样例 4

见附加文件中的 puzzle4.in 和 puzzle4.ans。

该样例满足测试点 $6$ 的限制。

样例 5

见附加文件中的 puzzle5.in 和 puzzle5.ans。

该样例满足测试点 $25$ 的限制。

输入格式

本题有多组测试数据。

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个整数 $k$；
• 接下来 $k$ 行，每行包含一个长度相同的正整数，依次表示 $a_1,a_2,\ldots,a_k$。

输出格式

对于每组测试数据，输出一行一个整数，表示合法列重排数量对 $998244353$ 取模后的结果。

提示

对于所有测试数据，保证：

• $1\le T \le 5\times10^5$；
• $3\le k\le 6$；
• $1\le n,\sum n\le 5\times 10^5$；
• 输入中的所有整数均没有前导零。

• 特殊性质 A：保证每组测试数据中 $n \le 8$。
• 特殊性质 B：保证 $k=3$。
• 特殊性质 C：如果允许重排后的整数出现前导零，则至少存在一种列重排满足加法等式。
• 特殊性质 D：保证每一列都可以作为某种进位状态下的合法竖式加法列。