​ 众所周知，一个矩形有长和宽两个维度。而对于长和宽都为整数的矩形而言，我们总可以发现一个边长为整数的单位正方形，使得矩形可以被完美分割成若干个该单位正方形（分割的每个单位正方形边长相等）。

聪明的580认为这太无趣了！

因为显然的，在长和宽都为整数的情况下，总有边长为 1 的单位正方形是成立的。所以580希望在接下来的游戏中，对于每一个长方形，寻找其最大的单位正方形（例如 2 \times 6 的矩形，其最大单位正方形是 2 \times 2）。

由于C语言程序设计的课程过于无聊，580决定在桌面上用鼠标框选应用程序玩。

580不会整理桌面，因此桌面是满的。我们将桌面视为一个 N\times N 的网格，由 N\times N 个边长为1的小正方形（应用程序）组成。

每次游戏中，580会将鼠标放在第一行第一列的应用程序左上角，按下鼠标左键，随后拖动鼠标随机甩出一段距离后松手，使得桌面上形成了一个矩形的选择框。

580练就神功，保证矩形选择框的右下角一定是随机的（即等概率地选取任意一个应用程序的右下角坐标）。

善（闲）于（得）探（蛋）索（疼）的580突发奇想，希望知道对于每次游戏框选的矩形，其最大单位正方形的边长的期望是多少。

为了使答案不涉及分数或小数，请将答案乘以 N^2 后对 998244353 取模输出。

形式上，请求出 \sum_{i=1}^n \sum_{j=1}^n \gcd(i,j) 对 998244353 取模后的结果

输入仅一个整数 N~(1\leq N \leq 5\cdot 10^6)

输出仅一个整数，表示答案对 998244353 取模后的结果

gcd(a,b) 表示 a 与 b 的最大公约数