Problem Statement

You are given an integer $N$. Find the number, modulo $998244353$, of sequences $A$ of length $N$ whose elements are each one of $1, 2, -1, -2$ and which satisfy the following condition.

• There exists a way to split the sequence $A$ into $1$ or more non-empty intervals such that, in every interval after the split, the product of the elements in the interval is $8$.
• More precisely, there exist a positive integer $L$ and an integer sequence $B$ of length $L$ satisfying $0 = B_1 < B_2 < \dots < B_L = N$ such that the following condition holds.
• $A_{B_i + 1} \times A_{B_i + 2} \times \dots \times A_{B_{i+1}} = 8 \ (1 \leq i \leq L - 1)$

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

Constraints

• All input values are integers.
• $1 \leq T \leq 888$
• $1 \leq N \leq 8.88 \times 10^{17}$

Input

The input is given from standard input in the following format, where $\mathrm{case}_i$ denotes the $i$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each case is given in the following format.

$N$

Output

Output $T$ lines. The $i$-th line should contain the answer to the $i$-th test case.

Sample

8
1
3
4
8
88
888
888888888
888000000000000000

0
4
32
9200
744976062
355614226
995875110
722933621