Let's define a sequence of Gray Codes $$$G_n$$$ as follows:

• if $$$n = 0$$$ then $$$G_n$$$ = {0},
• if $$$n \gt 0$$$ then $$$G_{n}$$$ is equal to $$$G_{n - 1} \cdot R(G_{n - 1} + 2^{n-1})$$$, where $$$\cdot$$$ means the concatenation of sequences, $$$R(s)$$$ means the reverse of sequence $$$s$$$ and $$$s + c$$$ means sequence $$$s$$$ with every number increased by a constant $$$c$$$.

For example, $$$G_1 = \{0, 1\}$$$, $$$G_2 = \{0, 1, 3, 2\}$$$ and $$$G_3 = \{0, 1, 3, 2, 6, 7, 5, 4\}$$$. For a Gray Code $$$G_n$$$, we define a $$$n \times 2^n$$$ table $$$T_n$$$. The cell in the $$$i$$$-th row and $$$j$$$-th column of $$$T_n$$$ is equal to the $$$i$$$-th least significant bit of the $$$j$$$-th number in the sequence $$$G_n$$$.

0	1	1	0	0	1	1	0
0	0	1	1	1	1	0	0
0	0	0	0	1	1	1	1

The table $$$T_3$$$

Your task is to answer $$$q$$$ queries. In each query, you are given a number $$$n$$$ and your task is to calculate the number of non-empty rectangles in the table $$$T_n$$$ that contain only $$$1$$$'s modulo 998 244 353.

3
1
2
3

1
7
32