题目描述

西西酱累了，于是直接丢给你一道数学题。

定义函数 $F(a, b)$ 表示有多少个有序数对 $(x, y)$ 满足 $x$, $y$ 能同时整除 $a$ 和 $b$。

• 例如：$F(4, 6) = 4$，对应 $(1, 1), (1, 2), (2, 1), (2, 2)$

现在西西酱指定了一个 $N$，让你计算 $\sum_{i=1}^{N} \sum_{j=1}^{i} F(i, j)$ 是多少。

换句话说，枚举 $1 \sim N$ 范围内的每个 $i$，再枚举 $1 \sim i$ 范围内的每个 $j$，计算 $F(i, j)$ 的总和是多少。

答案可能很大，输出答案对 $998244353$ 取模的结果。

输入格式

第一行一个整数 $T$，表示数据组数。

对于每组数据，包含一行，一个整数 $N$，如题所述。

输出格式

每组数据输出一行，一个整数，表示求和式对 $998244353$ 取模的结果。

样例

【样例 1 输入】

7
2
5
50
500
5000
50000
5000000

【样例 1 输出】

6
35
4878
507589
51320164
147901422
342983243

【样例 1 解释】

对于第一组数据有 $F(1, 1) = 1$，$F(2, 1) = 1$，$F(2, 2) = 4$

数据范围与提示

所有测试数据的范围和特点如下表所示：

对于所有测试点，保证 $1 \le N \le 5 \times 10^6$。

来源

• 简洁的数学