Wtd is a clever boy, he is very good at Discrete Math. Now he wants to test your level of mathematics. The test problem is easy: For given integer \(n\), you need to calculate \(\sum_{1 \leq x < y \leq n, x + y \geq n} \frac{1}{xy}[gcd(x,y)==1]\).
The first line contains an integer \(T(1\leq T \leq 10^4)\), denoting the number of test cases.
For each test case, there's an integer \(n(2\leq n \leq 10^8)\).
The answer can be represented as a fraction \(\frac{Q}{P}\), where \(gcd(P,Q)=1\) and \(P,Q>0\). You only need to print \(Q·P^{-1}\) mod \(998244353\) for each test case in a single line.
3
2
3
4499122177
1
831870295