P17269 [ICPC 2017 Urumqi R] Sum of the Line

考虑一个整数三角形，记为 $T$。位于 $(r,c)$ 处的值记为 $T_{r,c}$，其中 $1 \le r$ 且 $1 \le c \le r$。若 $r$ 和 $c$ 的最大公约数恰好为 $1$，则 $T_{r,c} = 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$ 所得的余数。

翻译由 DeepSeek V4 Pro 完成