Problem Statement

You are given a grid with $4$ rows and $4N$ columns, and $4N$ T-shaped tetrominoes.

Nyaan decides to fill all the cells of the grid with tetrominoes so that the following conditions are satisfied.

• Each cell of the grid is covered by exactly $1$ tetromino.
• Tetrominoes may be rotated when placed.

Find the number of placements of tetrominoes satisfying the conditions, modulo $998244353$.

Here, arrangements that coincide by flipping or rotating the grid are considered different. Also, the tetrominoes are indistinguishable from each other.

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

Constraints

• All input values are integers.
• $1 \leq T \leq 100$
• $1 \leq N \leq 100$

Input

$T$
$\mathrm{case}1$
$\vdots$
$\mathrm{case}T$

$N$

Output

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

Sample

3
1
2
100

2
6
52834137