题目描述
给定整数 $n$, $k$，多次询问：
$$\sum_{i=1}^n \sum_{j=1}^n \texttt{lcm}(i,j)^k \bmod 998244353$$
输入格式
第一行 $2$ 个整数 $t,k$
接下来 $t$ 行，每行 $1$ 个整数 $n$，代表一组询问。
样例 #1
输入样例 #1
10 1
10
35
48
16
25
43
40
18
13
19输出样例 #1
2127
290564
1005484
13060
77689
665032
482124
20995
6313
27512样例 #2
输入样例 #2
10 1
999997760
999997324
999983809
999973733
999998723
999968414
999985982
999987864
999970853
999975617输出样例 #2
536695821
193815221
376262448
88557790
473946792
220441071
596596951
210433689
909891309
526803728样例 #3
输入样例 #3
5 2
999997760
999997324
999983809
999973733
999998723输出样例 #3
711073035
17964514
547983764
710950027
104980738样例 #4
输入样例 #4
10 33
999991214
999998563
999987177
999972030
999971607
999987279
999988077
999978771
999994670
999999365输出样例 #4
976207931
469500131
139176898
723784784
460131733
535501296
157121994
549689698
430509703
280270755对于所有数据，$1\le t\le 100, 1 \le n \le 10^9,1\le k \le 1000$
子任务1（5分） ： $k=1,n\le 10^6$
子任务2（5分） ： $k=1,n\le 10^7$
子任务3（10分）： $k=1,n\le 10^9$
子任务4（15分）： $k=2,n\le 10^5$
子任务5（25分）： $k=2,n\le 10^9$
子任务6（40分）： 无特殊限制。