题目描述

考虑一个整数三角形，记为 $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$ 所得的余数。

2
2
3

1
5

提示

翻译由 DeepSeek V4 Pro 完成