# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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

.

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)**.

For each test case, output the value of `$(P Q ^{-1})$`

mod `$998244353$`

.

Input | Output |
---|---|

3 1 2 4 | 1 415935148 393751940 |

For **N = 2**, the probability of alex winning the game is `$\frac{11}{12}$`

.