Alex is participating in a game show. Mr. Phil is the host of the game. Alex is provided with an array containing N distinct integers from 1 to N. Mr. Phil has the same copy of the array. There are two phases of the game.
Phase 1: A wheel is rolled. The wheel will show a random integer in between 0 and N. Let the number be X. Then X integers will be randomly selected from Alex's array and removed. Now Mr. Phil's array contains N integers, but Alex's array contains N - X integers.
Phase 2: Again the wheel is rolled. This time the wheel will show a random integer between 0 and N - X. Let the number be K. Mr. Phil will randomly pick K integers from his array. If Alex's array contains all these K integers that were selected by Mr. Phil, then Alex wins.
Here is a simulation of the game.
Suppose N = 3. Initially Alex's array is [1 2 3] and Mr. Phil's array is [1 2 3]
In phase 1, the wheel shows X = 1. So 1 integer will be removed from Alex's array. Let it be number 2. So currently Alex's array is [1 3] and Mr. Phil's array is [1 2 3].
In phase 2, the wheel shows K = 2. So Mr. Phil will randomly pick 2 integers from his array.
If he picks [1 3], Alex wins.
If he picks [1 2] or [2 3], Alex loses.
You have to find the probability of Alex winning the game. The probability can be written in form $\frac{P}{Q}$, where $P$ and $Q$ are relatively prime integers and $Q \neq 0$ mod $998244353$ . You have to print the value of $(P Q ^{-1})$ mod $998244353$.
Input
First line contains an integer T (1 ≤ T ≤ 5000) denoting the number of test cases.
Each of the next T lines contain an integer N (1 ≤ N ≤ 30000000).
Output
For each test case, output the value of $(P Q ^{-1})$ mod $998244353$.
Sample
| Input | Output |
|---|---|
3 1 2 4 | 1 415935148 393751940 |
For N = 2, the probability of alex winning the game is $\frac{11}{12}$.
