C. Add
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a sequence of length $$$n$$$, $$$a_1,a_2,\ldots,a_n$$$, initially $$$a_i=i$$$. Perform $$$n-1$$$ operations on the sequence, where the $$$i$$$-th operation involves choosing an integer $$$j$$$ uniformly at random from the range $$$[1,n-i]$$$, and setting $$$a_j$$$ to $$$a_j+2a_{n-i+1}$$$.

Find the value of $$$a_1$$$ modulo $$$998244353$$$ after all operations are completed.

Input

The first line contains a positive integer $$$T$$$ ($$$1\leq T\leq 10^4$$$), indicating the number of test cases.

Following are $$$T$$$ lines, each containing a positive integer $$$n$$$ ($$$1\leq n\leq 10^9$$$), representing the length of the sequence.

Output

$$$T$$$ lines, each containing an integer representing the value of $$$a_1$$$ modulo $$$998244353$$$.

Examples
Input
3
4
2
5
Output
30
5
55
Input
3
4
3
5
Output
30
14
55
Input
3
8
1
3
Output
204
1
14