题目背景

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$ 时：

$\text{lcm}_{i=1}^{n}i=60$，可以验证在 $[0,60)$ 内不存在其他的 $k$ 满足条件，故答案为 $6$。

对于 $100\%$ 的数据，满足 $3 \leq n \leq 2 \times 10^9$，$T \leq 1000$。