D. 123 Matrix
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An $$$n \times n$$$ matrix $$$a$$$ is called good only if all of the following conditions are satisfied:

  • $$$1 \le a_{i,j} \le 3$$$ for all $$$1 \le i \le n$$$, $$$1 \le j \le n$$$.
  • The bitwise XOR values of all elements in each row are $$$0$$$.
  • The bitwise XOR values of all elements in each column are $$$0$$$.
  • The sum of all elements of the matrix reaches the maximum possible value.

You are given an integer $$$n$$$. Your task is to find the number of good matrices of size $$$n \times n$$$.

Input

The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

Each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

Output

For each testcase, print the number of good matrices of size $$$n \times n$$$.

As the answer can be very large, print the answer modulo $$$998244353$$$.

Example
Input
3
1
2
3
Output
0
1
12
Note

In the first test case, there is no valid good matrix.

In the second test case, $$$\begin{bmatrix} 3 & 3\\ 3 & 3 \end{bmatrix}$$$ is the only good matrix.