在数学中，函数 $d(n)$ 表示正整数 $n$ 的约数个数。 例如，$d(12) = 6$，因为 $1, 2, 3, 4, 6$ 和 $12$ 都是 $12$ 的约数。 在本题中，给定 $l, r$ 和 $k$。你的任务是计算以下式子：
$$\left( \sum_{i=l}^{r} d(i^k) \right) \pmod{998\,244\,353}$$
输入格式
输入的第一行包含一个整数 $T$ ($1 \le T \le 15$)，表示测试用例的数量。 每个测试用例占一行，包含三个整数 $l, r$ 和 $k$ ($1 \le l \le r \le 10^{12}, r - l \le 10^6, 1 \le k \le 10^7$)。
输出格式
对于每个测试用例，输出一行，包含一个整数，即该测试用例的答案。
样例
样例输入 1
3 1 5 1 1 10 2 1 100 3
样例输出 1
10 48 2302