Description

After learning that pneumonia broke out in City W, scientists immediately began intensive research.

(The following part is not rigorous science. Do not take it seriously outside of solving this problem.)

Suppose a certain virus has a spreading ability $D(x)$ on day $x$. The meaning of this function is the number of divisors of $x$. For example, $D(6)=4, D(7)=2$.

Now you are given the total number of spreading days $n$ and an influence constant $k$. You need to compute $\sum_{i=1}^n D(i^k)$, that is, $D(1^k)+D(2^k)+D(3^k)+ \cdots +D(n^k)$.

Since the answer may be very large, output it modulo $998244353$.

Sample Explanation

$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$ has $1$ divisor: $1$;
$4$ has $3$ divisors: $1,2,4$;
$9$ has $3$ divisors: $1,3,9$;
$16$ has $5$ divisors: $1,2,4,8,16$;
$25$ has $3$ divisors: $1,5,25$.

The total is $15$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, indicating the number of test cases.

Each of the next lines contains two integers $n,k$, with the meaning as described above.

Output Format

Output $T$ lines in total, where each line is the answer for one test case.

1
5 2

15

Hint

• For $20\%$ of the testdata, $1\leq T\leq 10,1\leq n\leq 100,1\leq k\leq 6$.
• There is another $30\%$ of the testdata where $1 \leq T \leq 10^4,1\leq n \leq 10^7,k=1$.
• For $100\%$ of the testdata, $1 \leq T \leq 10^4,1\leq n,k \leq 10^7$.

Translated by ChatGPT 5