Symmetrical Plant Arrangements

You are given an integer n representing the number of plants arranged in a row. A symmetrical arrangement of plants satisfies the following conditions:

• If n is even, the number of symmetrical arrangements is \(2^{n/2} \bmod 998244353\).
• If n is 1 or any odd number greater than 1, the number of symmetrical arrangements is 1.

Given t test cases, for each test case output the number of symmetrical arrangements modulo \(998244353\>.

Note: All computations must be performed modulo \(998244353\). The formula for even numbers is given by:

\[ \texttt{ans} = 2^{n/2} \mod 998244353. \]

inputFormat

The input is read from standard input (stdin) and has the following format:

 t
 n1
 n2
 ...
 nt

Where t (\(1 \le t \le 10^5\)) is the number of test cases. Each of the following t lines contains one integer n (\(1 \le n \le 10^9\)).

outputFormat

For each test case, output the corresponding number of symmetrical arrangements modulo \(998244353\) on a separate line. The output should be written to standard output (stdout).

## sample

5
1
2
3
4
5

1
2
1
4
1

</p>