U175806 ZeTa的数论题

某天，$\zeta$ 正接受着天地君亲师的跪拜时，听到了身后传来了脚步声。 转过头去，只见 $\text{Lefty Dad}$ 讥笑地看着他：“自己都不掂量一下你手里有没有一把金刚钻，信不信我揭你老底!” $\zeta$ 慌了，喊到：“校领导都没能在你面前装孙子，有什么本事说我？” $\text{Lefty Dad}$ 淡淡地说：“做出这题你再说。”随后便消失了踪影。 $\zeta$ 听了很不爽，随便秒了这题后，找来牵着他鼻子走的学生,吼道：“你能 $\text{AKIOI}$ 吗？我说你不能，你不能，你不能，你 $\text{TM}$ 也不能！我要是你就把 $\text{IOI}$ 一届一届 $\text{AK}$ 掉！”然后随手将写着题的纸向上一扔后扬长而去。 $\zeta$ 走后十分得意。却不知你在人群中看到了这题，将要让 $\zeta$ 啪啪打脸…… ##### 注：$\zeta=\text{ZeTa}$

$\zeta$ 丢出了这样一个简洁的式子： 记 $f(t)=\sum\limits_{k=1}^t k\left[\gcd(k,t)=1\right]$ 对每个给定 $n$ 求 $\sum\limits_{i=1}^n \sum\limits_{j=1}^n (i^2+j^2+ij)f(\gcd(i,j))\bmod 998244353$

本题存在多组数据： 第一行为数据中 $n$ 的最大值 $N$ 与数据组数 $T$ 对接下来的 $T$ 行每行有一个数 $n$ ，你需要求出此时上述式子的值对 $998244353$ 取模。

输出共 $T$ 行，每行一个正整数代表此时上述式子的值。

对 $10\%$ 的数据 $N、T\leq 100$ 对 $50\%$ 的数据 $N\leq 5\times 10^5、T\leq10^3$ 对 $100\%$ 的数据 $N\leq 10^7、T\leq 10^4$ [加强版](https://www.luogu.com.cn/problem/U183339) $\color{white}题解见$[$\color{white}这里$](https://www.luogu.com.cn/blog/Y-B-X/ti-xie-u175806-zt-di-shuo-lun-ti-post)