약수의 개수 세기

수학에서 $d(n)$은 양의 정수 $n$의 약수의 개수를 나타내는 함수이다.

예를 들어 $1$, $2$, $3$, $4$, $6$, $12$가 모두 $12$의 약수이므로 $d(12) = 6$이다.

이 문제에서는 $l$, $r$, $k$가 주어진다. 다음 값을 계산하시오.

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

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \leq T \leq 15$)

각 테스트 케이스는 한 줄에 세 정수 $l$, $r$, $k$로 주어진다. ($1 \leq l \leq r \leq 10^{12}$, $r - l \leq 10^6$, $1 \leq k \leq 10^7$)

각 테스트 케이스마다 정수 하나를 한 줄에 출력한다. 그 정수는 해당 테스트 케이스의 답이다.