选择困难症

Parviz 认为，如果一道题有一个可以显著优化复杂度的方法而不去使用，那这题就是有遗憾的。 Alice 认为，任何算法难度大于思维难度的题，出在正式比赛中都是没有意义的。 猫猫认为，ta 是学数学学的。 $\textsf{linyue}$ 认为……啊？你们在说啥？ 很有喜剧效果的是这四个名字你可能都没法一下子对上号（

Alice 与 Bob 在下棋之余，也需要一些娱乐活动来放松身心，比如去小吃街吃饭。作为一名绅士，Bob 每次都让 Alice 选择要去吃哪家。这却让 Alice 犯了难——她有选择困难症。 小吃街有 $n$ 家饭店，在第 $i$ 家就餐需要 $i$ 元钱。如果预算为 $a$ 元，则可以选择前 $a$ 家餐厅。 在长期的纠结后，Alice 想到一种方法：她提前在心里想好一个非负整数 $k< \text{lcm}_{i=1}^{n} i$ ，在得知预算 $a$ 之后，选择在第 $(k$ $\text{mod}$ $a)+1$ 家餐厅就餐。 由于买棋盘与棋子的市场价格浮动，每次就餐的预算未必相同，但都是 $[2,n]$ 之间的整数。Alice 想每次都换换口味，希望对于不同的 $a$，最后选定的餐厅各不相同。她想要知道满足要求的 $k$ 的个数，但又忙于与 Bob 下棋没有时间算，于是只好求助于你啦。 形式化地说，对于给定的 $n$，你需要求有多少个整数 $k \in [0, \text{lcm}_{i=1}^{n}i)$ ，满足 $k\bmod 2,k\bmod3 ,..., k\bmod n$ 各不相同。答案对 $998244353$ 取模。

第一行一个整数 $T$，表示共有 $T$ 组数据。 接下来 $T$ 行，每行一个整数 $n$ ，含义见题面。

共 $T$ 行，每行一个整数，表示满足要求的 $k$ 的数量。

3
3
4
5

4
3
6

5
13860108
13850709
220000633
693439571
1004535809

188051653
724253523
444803502
370347248
425186012

**【样例解释1】** $n=3,4$ 时，$k$ 的取值集合分别为 $\{2, 3, 4, 5\}$ 、 $\{3, 10, 11\}$。 $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$，可以验证在 $[0,60)$ 内不存在其他的 $k$ 满足条件，故答案为 $6$。 | 测试点编号 | $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$ | 对于 $100\%$ 的数据，满足 $3 \leq n \leq 2 \times 10^9$，$ T \leq 1000$。