考虑一个整数三角形，记为 $T$。位于 $(r, c)$ 的值记为 $T_{r,c}$，其中 $1 \le r$ 且 $1 \le c \le r$。如果 $r$ 和 $c$ 的最大公约数恰好为 $1$，则 $T_{r,c} = c$，否则 $T_{r,c} = 0$。

现在，我们有另一个整数三角形，记为 $S$。位于 $(r, c)$ 的值记为 $S_{r,c}$，其中 $1 \le r$ 且 $1 \le c \le r$。$S_{r,c}$ 定义为求和 $\sum_{i=c}^{r} T_{r,i}$。

现在轮到你了。对于给定的正整数 $k$，你需要计算三角形 $S$ 中第 $k$ 行所有元素的总和。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10000$)，表示测试用例的数量。 每个测试用例包含一行，为一个整数 $k$（如上所述），满足 $2 \le k \le 10^8$。

输出格式

对于每个测试用例，计算 $S$ 中第 $k$ 行元素的总和，并输出其除以 $998244353$ 的余数。

样例

样例输入 1

2
2
3

样例输出 1

1
5