시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 512 MB 2 2 2 100.000%

문제

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

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

In this problem, you are given $l$, $r$ and $k$. Your task is to calculate the following:

$$\left( \sum_{i = l}^{r} d \left( i^k \right) \right)   \bmod 998\,244\,353\text{.}$$

입력

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

Each test case is given as a line containing three integers $l$, $r$ and $k$ ($1 \leq l \leq r \leq 10^{12}$, $r - l \leq 10^6$, $1 \leq k \leq 10^7$).

출력

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

예제 입력 1

3
1 5 1
1 10 2
1 100 3

예제 출력 1

10
48
2302