题目背景

本题目来自仓库 https://github.com/Disposrestfully/CCPC-CQ-2024/tree/main

题目描述

Menji 学习了加法和乘法。

Menji 有一些写着 $1\sim 9$ 的卡片，其中写着 $i$ 的有 $a_i$ 张。

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

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

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

输入格式

本题含有多组测试数据。

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

之后 $T$ 行，每行 $9$ 个非负整数 $a_1,a_2,\dots a_9 \ (0\leq a_i\leq 100,\sum\limits_{i=1}^9 a_i\geq 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

提示

附加文件中提供了样例 checker。