Menji has learned addition and multiplication.

Menji has some cards with numbers $1 \sim 9$ written on them, where there are $a_i$ cards with the number $i$ written on them.

In each step, Menji chooses two cards and replaces them with a new card that has either their sum or their product written on it.

It can be observed that after $\sum_{i=1}^{9} a_i - 1$ operations, only one card remains in Menji's hand. Menji wants to maximize the value of the number on this final card. However, because the number of cards is small, Menji cannot complete this task on his own, and he hopes you can help him find the maximum possible value of the final number.

Since the answer can be very large, you only need to output the value of the answer modulo $998244353$. Note that you need to output the maximum value modulo $998244353$, not the maximum value in the sense of modulo $998244353$.

Input

The input is read from standard input. This problem contains multiple test cases. The first line contains a positive integer $T$ ($1 \le T \le 1000$), representing the number of test cases. Following this are $T$ lines, each containing 9 non-negative integers $a_1, a_2, \dots, a_9$ ($0 \le a_i \le 100$, $\sum_{i=1}^{9} a_i \ge 1$).

Output

Output to standard output. Output $T$ lines, where the $i$-th line is the result of the maximum value of the final remaining number in the $i$-th test case modulo $998244353$.

Examples

Input 1

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

Output 1

54
108
1
10
90
90553232
143532368