题目描述

在得知 W 市爆发的肺炎之后，科学家们立刻投入了紧锣密鼓的研究之中。

（下面的部分非严谨科学，大家做题以外切勿当真）

假设某种病毒在第 $x$ 天的传播能力为 $D(x)$，该函数的含义为 $x$ 的约数个数。例如 $D(6)=4, D(7)=2$。

现在给定你总的传播天数 $n$ 和一个影响常数 $k$，你需要计算 $\sum_{i=1}^n D(i^k)$ 也就是 $D(1^k)+D(2^k)+D(3^k)+ \cdots +D(n^k)$。

由于答案可能很大，请对 $998244353$ 取模。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

接下来每行两个整数 $n,k$，意义如题所示。

输出格式

共 $T$ 行，表示每组数据的答案。

1
5 2

15

提示

• 对于 $20\%$ 的数据，满足 $1\leq T\leq 10,1\leq n\leq 100,1\leq k\leq 6$；
• 存在另外 $30\%$ 的数据，满足 $1 \leq T \leq 10^4, 1\leq n \leq 10^7,k=1$；
• 对于 $100\%$ 的数据，满足 $1 \leq T \leq 10^4, 1\leq n,k \leq 10^7$。

【样例解释】

$D(1^2)+D(2^2)+D(3^2)+D(4^2)+D(5^2)$
$=D(1)+D(4)+D(9)+D(16)+D(25)$
$=(1)+(3)+(3)+(5)+(3)$

1 有约数 1 个：1；
4 有约数 3 个：1，2，4；
9 有约数 3 个：1，3，9；
16 有约数 5 个：1，2，4，8，16；
25 有约数 3 个：1，5，25；

一共有15个