| Baozii Cup 3 |
|---|
| Finished |
There is an infinitely large $$$2$$$-dimensional grid. Initially, you are at $$$(0,0)$$$, and there is a set $$$S=\{(0,0)\}$$$. You will walk exactly $$$n$$$ steps on the grid. In each step:
Compute the expected size of $$$S$$$ after $$$n$$$ steps.
Formally, let $$$M = 998\,244\,353$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$). The description of the test cases follows.
The only line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
Note that there is no restriction on the sum of $$$n$$$ over all test cases.
For each test case, output the expected size of $$$S$$$.
4123114514
2249561091499122180340469626
| Name |
|---|


