409354: GYM103488 H Hile and Subsequences' MEX

Before we start, we need to declare a few definitions.

MEX

$$$MEX$$$ of a sequence is the smallest non-negative integer doesn't appears in the sequence. For example:

• $$$MEX$$$ of $$$[1,2,3,4]$$$ is $$$0$$$.
• $$$MEX$$$ of $$$[0,1,2,3,4]$$$ is $$$5$$$.
• $$$MEX$$$ of $$$[2,3,4,0,2]$$$ is $$$1$$$.

Subsequence

The sequence $$$b$$$ is a subsequence of the sequence $$$a$$$ if and only if it can be obtained by deleting zero or more elements in $$$a$$$ without changing the order of the remaining elements. For example:

• $$$[1,2,3,4]$$$ is a subsequence of of $$$[1,2,3,4]$$$
• $$$[1,4]$$$ is a subsequence of of $$$[1,2,3,4]$$$
• $$$[4,1]$$$ is not a subsequence of of $$$[1,2,3,4]$$$

Hile has a sequence $$$a$$$ with length of $$$n(n \leq 10^9)$$$. The $$$i$$$-th element of $$$a$$$ is $$$i-1$$$ (i.e. $$$a=[0,1,2\dots n-1]$$$). Please help Hile calculate the sum of $$$MEX$$$ of all subsequences of $$$a$$$.

Since the answer may be very large, please output the answer modulo $$$998244353$$$.

The first line contains an integer $$$t(1\le t \leq 10^5)$$$ — the number of test cases.

Each test case is described by one integer $$$n(1\le n\le 10^9)$$$ — the length of the sequence $$$a$$$.

Output $$$t$$$ lines, each line contains an integer — the answer modulo $$$998244353$$$.

2
4
1000000000

15
851104390