Make Numbers with Division

Sebin has several nonzero numbers.

Sebin lays out all of these numbers in a row without concatenating them, and writes one division sign between each pair of adjacent numbers. Then he adds parentheses as many times as he likes to form a valid expression, evaluates it, and tries to make a number.

Suppose Sebin has 1, 2, 3, 4, and 6. Sebin can make the following numbers.

• $(6 \div (4 \div 1) \div 3) \div 2 = 14$
• $(6 \div 3) \div (4 \div 1) \div 2 = 14$
• $(2 \div (3 \div 4)) \div (6 \div 1) = 49$
• $(4 \div 6 \div (1 \div 2)) \div 3 = 4$
• $4 \div (2 \div 1 \div (6 \div 3)) = 4$

The numbers that can be made this way are 1144, 136, 116, 19, 14, 49, 1, 94, 4, 9, 16, 36, and 144. That is 13 numbers in total.

Sebin has $A_i$ copies of the number $i$. Sebin wants to count how many numbers he can make. The number of ways to arrange the numbers and the number of ways to place parentheses both grow very quickly as the count increases, so Sebin needs help counting the numbers he can make.

The first line contains the number of test cases $T$. ($1 \le T \le 10^5$)

Each test case is given on one line with 9 integers $A_i$ separated by spaces. ($0 \le A_i \le 10^9$, $1 \le \sum A_i$)

For each test case, print on one line the number of numbers that can be made, modulo 998 244 353.