問題文

$3\times 3$ のマス目があり、最初はどのマスにもなにも書き込まれていません。
これから、次の条件がすべて満たされるようにそれぞれのマスに正の整数を一つずつ書き込みます。
ただし、上から $i+1$ 番目、左から $j+1$ 番目のマス目( $0\le i, j < 3$ )に書き込まれた数を $A_{ij}$ とします。
・$i=0,1,2$ について、$A_{i0}A_{i1}A_{i2}=K$ が成り立つ。
・$j=0,1,2$ について、$A_{0j}A_{1j}A_{2j}=K$ が成り立つ。

つまり、縦、横に並ぶ $3$ つの整数からなる組すべてについて、それらの積がちょうど $K$ になるように書き込みます。 このような書き込み方の総数を $998244353$ で割った余りを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

入力

$T$
$case_1$
$case_2$
$case_3$
$\vdots$
$case_T$

$K$

入力は以下の制約を満たします。
・ 入力はすべて整数
・ $1 \le T \le 10^5$
・ $1 \le K \le 10^6$

出力

$T$ 行出力してください。$i$ 行目には、$i$ 個目のテストケースの答えを出力してください。 最後に改行してください。

サンプル

3
108
1
120

1155
1
1980

2 6 9
6 9 2
9 2 6