시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 512 MB333100.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