CuOI R1 - Flashing Thread

题目背景

你的视线逐渐模糊，你看见她的身躯不断幻化，剥离出条条丝线，散落到那洁白天地之下的深渊中。

题目描述

深渊中是一个 $ n \times n $ 的矩阵，矩阵格子边长为 $ 1 $。Cuset 幻化成的丝线飘到矩阵上时会增加矩阵的「闪烁度」。最终矩阵增加的「闪烁度」为每个格子增加的「闪烁度」之和，第 $ i $ 个格子增加的「闪烁度」之和定义为 $ \gcd(x_i, y_i) $ ，$ {x_i,y_i} $ 为一个格子的横、纵坐标。

由于深渊的黑暗，「闪烁度」会流失一些，那些横、纵坐标互质的格子，「闪烁度」会流失 $ 1 $。

每个格子「闪烁度」的初始值为 $ \textbf{71002} $。

请你算出最终矩阵每个格子的「闪烁度」之和，由于数据可能很大，请输出最终答案模 $ 998244353 $ 的结果。

注意：一个测试点内有多组测试数据。

输入格式

第一行一个数 $ t $，表示测试数据组数。

接下来共 $ t $ 行，每行一个数，$ n $，表示矩阵的边长。

输出格式

$ t $ 行，每行一个数，该组测试数据中矩阵所有格子「闪烁度」之和模 $ 998244353$ 结果。

样例 #1

样例输入 #1

1
3

样例输出 #1

213011

样例 #2

样例输入 #2

1
5

样例输出 #2

355028

提示

数据范围

subtask 1：$ 0 < n \le 5000, 0 < t \le 5 $

subtask 2：$ 0 < n \le 10^3, 0 < t \le 250 $

subtask 3：$ 0 < n \le 10^7, 0 < t \le 10^3 $

对于 $ 100% $ 的数据，$ 0 < n \le 10^7, 0 < t \le 10^3 $。