H. One Punch MEX
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The contest arena is under attack ! George wants to save it, so he will use his special ability called "One Punch MEX".

George has $$$n$$$ power stones numbered from $$$1$$$ to $$$n$$$. For $$$n$$$ times the following action will happen in order:

  1. Uniformly at random, one of the stones will disappear
  2. The MEX of the remaining stones will add to the One Punch MEX damage

George is wondering what will be the expected damage of the One Punch MEX if he has $$$n$$$ power stones

MEX is the minimum positive number not present in the set. MEX of $$$[]$$$ is $$$1$$$, MEX of $$$[3,5,1]$$$ is $$$2$$$

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows

The first line of each test case contains a single integer $$$n$$$ $$$( 1 \le n \le 10^{5} )$$$ indicating the number of power stones

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{5}$$$

Output

For each test case, output a single line containing the expected damage of One Punch MEX modulo $$$998244353$$$

Example
Input
2
1
2
Output
1
499122179
Note

In the second test case:

George has stones [1, 2]

With the probability $$$\frac{1}{2}$$$, the first stone will be removed, then the second stone with the sum of MEX equal to 2

With the probability $$$\frac{1}{2}$$$, the second stone will be removed, then the first stone with the sum of MEX equal to 3

The expected damage of One Punch MEX is $$$\frac{5}{2}$$$