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*}

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)$.

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