408724: GYM103274 B Basel Problem
Description
In 1734, the great mathematician Leonhard Euler solved the famous Basel Problem, which states that $$$\displaystyle \sum_{k=1}^{\infty} \frac{1}{k^2} = \frac{\pi^2}{6} $$$.
He also provided a generalization: let $$$n$$$ be an even positive integer, then the function $$$\displaystyle \zeta(n) = \sum_{k=1}^{\infty} \frac{1}{k^n}$$$ is always equal to a rational multiple of $$$\pi^n$$$, i.e., $$$\displaystyle \zeta(n) = \frac{p_n}{q_n} \pi^n$$$ for some positive integers $$$p_n$$$ and $$$q_n$$$ with $$$gcd(p_n, q_n) = 1$$$.
Almost 300 years later, another great mathematician insert your name here found a way to compute $$$p_n$$$ and $$$q_n$$$ very fast, but since those numbers can be very large, he really finds $$$p_n \times q_n^{-1}\ mod\ 998244353$$$ only, where $$$q_n^{-1}$$$ is the multiplicative inverse of $$$q_n$$$ in that modulo.
InputThe first line of input contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$), representing the number of test cases. Each of the following $$$T$$$ lines contain an even positive integer $$$n$$$ ($$$2 \leq n \leq 2 \times 10^5$$$).
OutputFor each test case output the value of $$$p_n \times q_n^{-1}\ mod\ 998244353$$$. It can be shown that under the constraints given, $$$q_n \not\equiv 0\ mod\ 998244353$$$.
ExampleInput5 2 4 6 8 10Output
166374059 144190851 13732462 600319858 766467710Note
$$$\displaystyle \zeta(2) = \frac{1}{6}\pi^2$$$
$$$\displaystyle \zeta(4) = \frac{1}{90}\pi^4$$$
$$$\displaystyle \zeta(6) = \frac{1}{945}\pi^6$$$
$$$\displaystyle \zeta(8) = \frac{1}{9450}\pi^8$$$
$$$\displaystyle \zeta(10) = \frac{1}{93555}\pi^{10}$$$