수 만들기

세빈이에게는 0이 아닌 숫자가 여러 개 있다.

세빈이는 이 숫자들을 이어 붙이지 않고 일렬로 모두 나열한 뒤, 숫자 사이사이에 나눗셈 기호를 하나씩 적었다. 그런 다음 괄호를 원하는 만큼 쳐서 올바른 수식을 만들고, 계산해서 수를 만들려고 한다.

세빈이가 1, 2, 3, 4, 6을 가지고 있다고 해 보자. 세빈이는 다음과 같은 수들을 만들 수 있다.

• $(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$

이런 식으로 만들 수 있는 수는 1144, 136, 116, 19, 14, 49, 1, 94, 4, 9, 16, 36, 144로 모두 13가지이다.

숫자 $i$가 $A_i$개 있을 때 만들 수 있는 수의 개수를 구하려고 한다. 숫자가 많아지면 나열하는 방법도, 괄호를 치는 방법도 크게 늘어나서, 세빈이는 만들 수 있는 수의 개수를 세는 데 어려움을 겪고 있다. 세빈이를 도와 만들 수 있는 수의 개수를 구하자.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10^5$)

각 테스트 케이스마다 한 줄에 공백으로 구분된 9개의 정수 $A_i$가 주어진다. ($0 \le A_i \le 10^9$, $1 \le \sum A_i$)

각 테스트 케이스마다 한 줄에 만들 수 있는 수의 개수를 998 244 353으로 나눈 나머지를 출력한다.