시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
7 초 | 512 MB | 5 | 4 | 4 | 80.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.
3 1 5 1 1 10 2 1 100 3
10 48 2302