Counting Divisors

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

Description

In mathematics, the function $d(n)$ denotes the number of divisors of positive integer $n$.

For example, $d(12)=6$ because $1,2,3,4,6,12$ are all $12$'s divisors.

In this problem, given $l,r$ and $k$, your task is to calculate the following thing :

\begin{eqnarray*}
\left(\sum_{i=l}^r d(i^k)\right)\bmod 998244353
\end{eqnarray*}

Input

The first line of the input contains an integer $T(1\leq T\leq15)$, denoting the number of test cases.

In each test case, there are $3$ integers $l,r,k(1\leq l\leq r\leq 10^{12},r-l\leq 10^6,1\leq k\leq 10^7)$.

Output

For each test case, print a single line containing an integer, denoting the answer.

Sample Input

3 1 5 1 1 10 2 1 100 3

Sample Output

10 48 2302

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码