题目描述
Problem Background
Parviz believes that if a problem has a method that can significantly optimize complexity but is not used, then the problem is regrettable.
Alice believes that any problem with algorithmic difficulty greater than thinking difficulty is meaningless in formal competitions.
The cat believes that it is due to studying mathematics.
$\textsf{linyue}$ thinks... huh? What are you talking about?
It's quite comical that you might not be able to match these four names right away.
Problem Description
Aside from playing chess, Alice and Bob also need some recreational activities to relax, such as dining at the snack street. As a gentleman, Bob always lets Alice choose which restaurant to go to. This, however, makes Alice struggle—she has indecisive dilemma.
There are $n$ restaurants on the snack street, and dining at the $i$-th restaurant costs $i$ yuan. If the budget is $a$ yuan, then the first $a$ restaurants can be chosen.
After a long period of hesitation, Alice came up with a method: she would think of a non-negative integer $k < \text{lcm}_{i=1}^{n} i$ in advance. After knowing the budget $a$, she would choose to dine at the $(k \mod a) + 1$-th restaurant.
Due to the fluctuating market prices for chessboards and pieces, the budget for each meal may not be the same, but it will always be an integer between $[2, n]$. Alice wants to try different flavors each time, hoping that for different $a$, the chosen restaurants will be different. She wants to know the number of $k$ that meet the requirements, but she is too busy playing chess with Bob to calculate, so she has to ask for your 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 different. The answer should be taken modulo $998244353$.
Input Format
The first line contains an integer $T$, indicating the number of test cases.
The next $T$ lines each contain an integer $n$, as described in the problem statement.
Output Format
There will be $T$ lines in total. Each line contains an integer representing the number of $k$ that meet the requirements.
Sample Input and Output
Sample Input #1
3
3
4
5
Sample Output #1
4
3
6
Sample Input #2
5
20070328
20061001
220000633
693439571
1004535809
Sample Output #2
322425494
609683002
444803502
370347248
425186012
Notes
[Sample Explanation 1]
For $n=3,4$, the sets of $k$ are $\{2, 3, 4, 5\}$ and $\{3, 10, 11\}$, respectively.
For $n=5$:
| $k$ | $k \bmod 2$ | $k \bmod 3$ | $k \bmod 4$ | $k \bmod 5$ |
|---|---|---|---|---|
| $27$ | $1$ | $0$ | $3$ | $2$ |
| $34$ | $0$ | $1$ | $2$ | $4$ |
| $35$ | $1$ | $2$ | $3$ | $0$ |
| $39$ | $1$ | $0$ | $3$ | $4$ |
| $58$ | $0$ | $1$ | $2$ | $3$ |
| $59$ | $1$ | $2$ | $3$ | $4$ |
$\text{lcm}_{i=1}^{n} i = 60$, and it can be verified that there are no other $k$ within $[0, 60)$ that satisfy the condition, so the answer is $6$.
| Test Case Number | $T \leq$ | $n \leq$ |
|---|---|---|
| $1-2$ | $15$ | $15$ |
| $3-6$ | $1000$ | $1000$ |
| $7-12$ | $1000$ | $2 \times 10^7$ |
| $13-20$ | $15$ | $2 \times 10^9$ |
For $100\%$ of the data, it is guaranteed that $3 \leq n \leq 2 \times 10^9$ and $T \leq 1000$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分