Practice on Toph

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

Game Show

By fsshakkhor · Limits 2s, 1.0 GB

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

InputOutput
3
1
2
4
1
415935148
393751940

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

Discussion

Statistics


100% Solution Ratio

steinumEarliest, 2w ago

steinumFastest, 0.5s

steinumLightest, 481 MB

steinumShortest, 828B

Submit

Login to submit