小 \(C\) 喜欢三元组。他认为一个整数三元组 \((x,y,z)\) 是美丽的，当且仅当 \(1 \le x,y,z \le n,xy\le n,yz \le n,xz\le n\) ，其中 \(n\) 是给定的正整数。

小 \(U\) 想为难一下小 \(C\) ，于是他向小 \(C\) 提出了 \(T\) 个问题，每个问题包含一个正整数 \(n\) ，你需要帮小 \(C\) 回答有多少个美丽的三元组。

答案对 \(998244353\) 取模。

输入格式

第一行包含一个整数 \(T\) 。

以下 \(T\) 行，每行一个整数 \(n\) ，表示一个问题。

输出格式

\(T\) 行，每行一个整数，表示对应问题的答案。

样例输入 1

3
1
2
5

样例输出 1

1
4
17

样例解释

对于第 \(1\) 组数据，满足条件的三元组为 \((1,1,1)\) 。

对于第 \(2\) 组数据，满足条件的三元组为 \((1,1,1),(1,1,2),(1,2,1),(2,1,1)\) 。

样例输入 2

见下发文件中的 ex_triple2.in 。该样例满足数据点 3,4 的限制。

样例输出 2

见下发文件中的 ex_triple2.out 。该样例满足数据点 3,4 的限制。

样例输入 3

见下发文件中的 ex_triple3.in 。该样例满足数据点 5,6 的限制。

样例输出 3

见下发文件中的 ex_triple3.out 。该样例满足数据点 5,6 的限制。

样例输入 4

见下发文件中的 ex_triple4.in 。该样例满足数据点 9,10 的限制。

样例输出 4

见下发文件中的 ex_triple4.out 。该样例满足数据点 9,10 的限制。

数据范围

令 \(N=\max n\) 。

数据点编号	附加限制
1,2	\(N \le 100\)
3,4	\(N \le 2 \times 10^3\)
5,6	\(N \le 5 \times 10^5\)
7,8	\(N \le 10^7\)
9,10	无

对于所有数据，保证 \(T \le 100,1 \le n \le 10^9\) 。

下发文件

a_little_cut Round 2 下发文件