Problem K: Discrete Math Is Simple

Problem K: Discrete Math Is Simple

Time Limit: 5 Sec  Memory Limit: 512 MB
Submit: 12  Solved: 4
[Submit][Status][Web Board]

Description

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]\).


Input

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

Output

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.


Sample Input

3
2
3
4

Sample Output

499122177
1
831870295

HINT

[Submit][Status]