题目背景

月下的轻花，随轻风飘舞，勾起了你我的记忆......

题目描述

在轻花林中，有从 $l$ 到 $r$ 编号的轻花树，编号为 $i$ 的树有 $i-1$ 棵，轻花林很美，所以每棵树上都有编号为 $1\sim n$ 的 $n$ 朵轻花，编号为 $i$ 的树上编号为 $j$ 的轻花落下会产生大小为 $\left\lceil\log_ij\right\rceil$ 的魅力值。

夜幕降临，所有树上的所有轻花全部落下，花痴（雾）tlx 想知道总共有多大的魅力值，但是只算一次太简单了，所以他会设置不同情境询问你 $T$ 次，不过由于答案很大，你只需要告诉他魅力值总和对 $998244353$ 取模的结果。

一句话题意： $T$ 组询问，每次给定三个整数 $l,r,n$，求出下式的值：

$$\sum_{i=l}^r(i-1)\sum_{j=1}^n \left\lceil\log_ij\right\rceil\;\;\bmod998244353 $$

输入格式

第一行一个整数 $T$，代表询问个数。

接下来 $T$ 行，每行三个整数 $l,r,n$，分别代表树编号的起始值，终止值，以及一棵树上轻花的朵数。

输出格式

共 $T$ 行，每行一个整数，代表每一个询问的结果对 $998244353$ 取模的结果。

1
2 3 5

20

2
23333 23333 233233
114514 19260817 1919810   

356712294
125194507

提示

【数据范围与约束】

本题采用捆绑测试，具体约束如下：

• Subtask 1 $(1\text{ pts})$：$T=1$，$n=1$；
• Subtask 2 $(9\text{ pts})$：$l=r=2$；
• Subtask 3 $(10\text{ pts})$：$T=1$，$n\leq 10^3$，$r\leq 10^3$；
• Subtask 4 $(10\text{ pts})$：$l=r\not=2$；
• Subtask 5 $(20\text{ pts})$：$T=1$，$n\leq 10^6$；
• Subtask 6 $(20\text{ pts})$：$T=1$，$r\leq 10^6$；
• Subtask 7 $(20\text{ pts})$：$T\leq 3000$；
• Subtask 8 $(10\text{ pts})$：无特殊限制，时间限制 $1.5\;\text{s}$。

对于所有数据，满足：

$1\leq T\leq 10^5$，$1\leq n\leq 10^{18}$，$2\leq l\leq r\leq 10^{18}$。

注意：在具体约束中没有提到的数据范围均为极限数据范围。

---

【样例解释 #1】

$$\left\lceil\log_21\right\rceil+\left\lceil\log_22\right\rceil+\left\lceil\log_23\right\rceil+\left\lceil\log_24\right\rceil+\left\lceil\log_25\right\rceil=8 $$$$\left\lceil\log_31\right\rceil+\left\lceil\log_32\right\rceil+\left\lceil\log_33\right\rceil+\left\lceil\log_34\right\rceil+\left\lceil\log_35\right\rceil=6 $$

故：

$$ans=8×(2-1)+6×(3-1)=20$$

对于样例 #2，我相信您聪明的大脑可以分分钟得到答案的。

---

【其他提示】

如果你不了解对数（$\log$）运算,可以查看这里。