T237727 Beliefs

小 C 是一名再朴素不过的 OIer。 从第一天学习 OI 起，NOI Au 的理想，就深植于他的心中。 为了信仰，他始终对未来充满希望。 ------------ 励志要比任何人都卷的他，却总发现前路荆棘密布，坎坷不平。 每一次又被同机房的神仙吊打的 CodeForces、AtCoder 的比赛，每一次 WA 了无数遍却仍然 debug 不出错误，每一次看不懂神仙们写的题解，每一次学不会那些别人都能秒切的新算法……每一次挫折，都在逐渐消灭小 C 心中如烈火般燃烧的信仰。 望着别人取得的成就，望着那遥不可及的分数，他很羡慕，也很无奈。 长夜漫漫，小 C 探索着、前行着。 ------------ 时间，见证了小 C 的成长。 随着 CF 和 ATC 的 rating 越来越高，随着 AC 的题数越来越多，随着写过的题解堆满了他的博客，小 C 与神仙们的差距也在缩小。 小 C 为自己的每一点进步感到兴奋。每当自己又上分时，那仿佛黑暗无边的路上，就多了一点微弱的亮光。 ------------ 省选 D2，离考试结束只剩 20min。 小 C 早已写完了 T2 和 T3 的暴力，他正向 T1 的正解发起挑战。 面对一分一秒流逝的时间，面对过不去的大样例，他默默的告诉自己，“我小 C 绝不认输，我小 C 永不言弃！！只要还有一秒钟，我都要坚持到底！！” 汗水从他的身上滚落，密密麻麻的过程写满了整张演算纸。他写下一行行代码，拼尽全力追逐着心中的梦想。 终于，他过了大样例。 ------------ 凭借着最后的绝杀，他进了 B 队。 他终于能够参加自己梦寐以求的 NOI，心中百感交集，难以言表。 他感到，光明就要来到他的眼前了。这种信仰不断的激励着他，他愈渴望成功，就愈发努力；愈追逐理想，就愈发坚强！

在 NOI 的考场上，小 C 看到了这一题： 有 $T$ 次询问，每次给定正整数 $n$，你需要求出 $$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\varphi\left(\operatorname{lcm}(i,j)^{\gcd(i,j)}\right)$$ 对 $998244353$ 取模的值。 有着深厚的数学功底的小 C 当然会做这一题，但是他看着复杂的式子，开始害怕自己会推错。 为了信仰，小 C 找到了你，希望你能写出一份代码来和他对拍。只剩下 $\text{3s}$ 的时间了，你能帮小 C 实现他的愿望吗？ 提示：这里的 $\varphi$ 表示欧拉函数；$\operatorname{lcm}(i,j)$ 表示 $i,j$ 的最小公倍数；$\gcd(i,j)$ 表示 $i,j$ 的最大公因数。

第一行为一个正整数 $T$，表示询问次数。 接下来 $T$ 行，每行一个正整数 $n$，含义见题目描述。

共 $T$ 行，每行一个正整数，表示答案。

**【样例 $1$ 解释】** 设 $f(i,j)=\varphi\left(\operatorname{lcm}(i,j)^{\gcd(i,j)}\right)$，则可以列出函数值的表格： |$i,j$|$1$|$2$|$3$|$4$|$5$|$6$|$7$| | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | |$1$|$1$|$1$|$2$|$2$|$4$|$2$|$6$| |$2$|$1$|$2$|$2$|$8$|$4$|$12$|$6$| |$3$|$2$|$2$|$18$|$4$|$8$|$72$|$12$| |$4$|$2$|$8$|$4$|$128$|$8$|$48$|$12$| |$5$|$4$|$4$|$8$|$8$|$2500$|$8$|$24$| |$6$|$2$|$12$|$72$|$48$|$8$|$15552$|$12$| |$7$|$6$|$6$|$12$|$12$|$24$|$12$|$705894$| 求和得到答案为 $724609$。 **【数据规模与约定】** |测试点编号|$n$|$T$| | :-----------: | :-----------: | :-----------: | |$1$|$\leqslant 10$|$\leqslant 10$| |$2$|$\leqslant 10^3$|$\leqslant 10$| |$3\sim4$|$\leqslant 2\times10^3$|$\leqslant10^5$| |$5\sim8$|$\leqslant 2\times10^4$|$\leqslant10^5$| |$9\sim12$|$\leqslant 2\times10^5$|$\leqslant10$| |$13\sim16$|$\leqslant 10^5$|$\leqslant 10^5$| |$17\sim20$|$\leqslant 1.5\times10^5$|$\leqslant 10^5$| |$21\sim25$|$\leqslant 2\times10^5$|$\leqslant 10^5$| 对于 $100\%$ 的数据，满足 $1\leqslant n\leqslant 2\times10^5,1\leqslant T\leqslant 10^5$。 ------------ 成绩公布，终于，小 C 取得了他梦寐以求的 NOI Au。 在经历了漫漫长夜后，那一缕明亮、柔和的光，照进了他的双眸。 未来、成功、光明、希望……一切看上去都那么美好。 回望过去走过的路，每一次尝试、每一点努力、每一次永不言弃、每一次坚持到底，都在他的眼前逐渐汇聚起来，如同点点星光，照亮了一路上的所有回忆。 一切汗水和泪水、一切奋斗和付出、一切痛苦与艰辛，都化成了甘甜，化成了美好，化成了只属于自己的，永远的回忆。 此刻，两行泪水从小 C 的眼睛里喷涌而出，顺着他的脸颊，缓缓流下。