Background

Parviz believes that if a problem has a method that can significantly optimize the complexity but you do not use it, then the problem is “regretful”.

Alice believes that any problem whose algorithmic difficulty is greater than the difficulty of thinking is meaningless in an official contest.

Cat-cat believes that they are studying mathematics.

$\textsf{linyue}$ believes... Huh? What are you talking about?

What is very funny is that you might not be able to match these four names to the right people right away.

Problem Description

Besides playing chess, Alice and Bob also need some entertainment activities to relax, such as going to the snack street to eat. As a gentleman, Bob lets Alice choose which restaurant to eat at every time. This makes Alice troubled—she has indecisiveness.

There are $n$ restaurants on the snack street. Eating at the $i$-th restaurant costs $i$ yuan. If the budget is $a$ yuan, then one can choose among the first $a$ restaurants.

After a long time of hesitation, Alice comes up with a method: she decides in advance a non-negative integer $k < \text{lcm}_{i=1}^{n} i$. After learning the budget $a$, she chooses to eat at the $(k$ $\text{mod}$ $a)+1$-th restaurant.

Because the market price of chessboards and pieces fluctuates, the budget for each meal may not be the same, but it is always an integer in $[2,n]$. Alice wants to change her taste each time, and hopes that for different $a$, the final chosen restaurants are all different. She wants to know the number of $k$ that satisfy the requirement, but she is busy playing chess with Bob and has no time to compute it, so she asks you for help.

Formally, for a given $n$, you need to find how many integers $k \in [0, \text{lcm}_{i=1}^{n}i)$ satisfy that $k\bmod 2, k\bmod 3, ..., k\bmod n$ are all distinct. Output the answer modulo $998244353$.

Input Format

The first line contains an integer $T$, indicating that there are $T$ test cases.

The next $T$ lines each contain an integer $n$, whose meaning is given in the statement.

Output Format

Output $T$ lines. Each line contains an integer representing the number of $k$ that satisfy the requirement.

3
3
4
5

4
3
6

5
13860108
13850709
220000633
693439571
1004535809

188051653
724253523
444803502
370347248
425186012

Hint

Sample Explanation 1

When $n=3,4$, the sets of possible values of $k$ are $\{2, 3, 4, 5\}$ and $\{3, 10, 11\}$, respectively.

When $n=5$:

$\text{lcm}_{i=1}^{n}i=60$. You can verify that there is no other $k$ in $[0,60)$ that satisfies the condition, so the answer is $6$.

For $100\%$ of the testdata, $3 \leq n \leq 2 \times 10^9$ and $T \leq 1000$.

Translated by ChatGPT 5