H. Hile and Subsequences' MEX
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Input

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

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

Example
Input
2
4
1000000000
Output
15
851104390