题目描述

Menji 学习了加法和乘法。 Menji 有一些写着 $1 \sim 9$ 的卡片，其中写着 $i$ 的有 $a_i$ 张。

Menji 每次会选择两张卡片，并选择将它们的和或者它们的积写在一张新的卡片上，之后他会丢弃选择的两张卡片，并拿起新的一张卡片。

可以发现，经过 $\sum_{i=1}^{9} a_i - 1$ 轮操作之后，Menji 手上只剩下一张卡片，Menji 想要最大化这张卡片上数字的值，但由于卡片数量太少，Menji 无法独立完成这个任务，希望你能帮他求出最后的数字最大能是多少。

由于本题答案很大，你只需要输出答案对 $998244353$ 取模后的值。注意，你需要输出的是最大值 $\bmod\ 998244353$，而不是 $\bmod\ 998244353$ 意义下的最大值。

输入格式

从标准输入读入数据。

本题含有多组测试数据。

第一行一个正整数 $T$ $(1 \le T \le 1000)$，表示数据组数。

之后 $T$ 行，每行 9 个非负整数 $a_1, a_2, \ldots, a_9$ $(0 \le a_i \le 100, \sum_{i=1}^{9} a_i \ge 1)$。

输出格式

输出到标准输出。

输出 $T$ 行，其中第 $i$ 行是第 $i$ 组数据中最终剩余的数的最大值对 $998244353$ 取模的结果。

样例

7
5 3 0 0 0 0 0 0 0
4 1 1 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 2
99 88 77 66 55 44 33 22 11
100 90 80 70 60 50 40 30 20

54
108
1
10
90
90553232
143532368