Problem Statement

There is a $3\times 3$ grid, and initially nothing is written in any of its cells.
You will now write one positive integer in each cell so that all of the following conditions are satisfied.
Here, let $A_{ij}$ denote the number written in the cell that is $i+1$-th from the top and $j+1$-th from the left ( $0\le i, j < 3$ ).
・For $i=0,1,2$, $A_{i0}A_{i1}A_{i2}=K$ holds.
・For $j=0,1,2$, $A_{0j}A_{1j}A_{2j}=K$ holds.

In other words, you write the numbers so that for every group of $3$ integers aligned vertically or horizontally, their product is exactly $K$. Find the total number of ways to write the numbers in this way, modulo $998244353$.

You are given $T$ test cases; answer each of them.

Input

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

$K$

The input satisfies the following constraints.
・ All input values are integers
・ $1 \le T \le 10^5$
・ $1 \le K \le 10^6$

Output

Print $T$ lines. On the $i$-th line, print the answer to the $i$-th test case. Print a newline at the end.

Sample

3
108
1
120

1155
1
1980

2 6 9
6 9 2
9 2 6