题目描述

Yuki 梦想前往那片不可到达之地，经过多年的努力，她的面前只剩下了这样一道题目。

给定三个整数 $a, b, m$。你需要进行 $m$ 轮操作，第 $i$ 轮操作可以令 $a \leftarrow a \bmod (m - i + 1)$ 或者不进行修改。求 $m$ 轮操作后 $a = b$ 的方案数，答案对 $998244353$ 取模。

定义两种方案不同，当且仅当存在 $1 \le i \le m$，使得一种方案中第 $i$ 轮进行了修改，而另一种方案中第 $i$ 轮没有进行修改。注意，只要选择执行 $a \leftarrow a \bmod (m - i + 1)$ 即视为进行了修改，不论修改后 $a$ 的值是否变化。

你曾经也幻想登上只存在于童话里的不可到达之地，如今 Yuki 有机会实现这个梦想，你必须帮助她。

输入格式

本题包含多组测试数据。

第一行包含一个正整数 $t$ $(1 \le t \le 10^5)$，表示测试数据组数。

对于每组测试数据：

• 共一行，包含三个整数 $a, b, m$ $(0 \le b < m \le a \le 2\cdot10^5)$。

保证所有测试数据的 $a$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示答案对 $998244353$ 取模的结果。

5
5 0 5
5 2 3
10 1 7
10 6 10
100000 114 514

25
1
14
0
837481226

提示

对于第 $1$ 组测试数据：

• 其中一种满足要求的操作方案为，在第 $3$ 轮操作中和第 $4$ 轮操作中进行修改。
• 另一种满足要求的操作方案为，在第 $1,2,3,4,5$ 轮操作中均进行修改。

对于第 $2$ 组测试数据：

• 唯一一种满足要求的操作方案为，在第 $3$ 轮操作中进行修改。

对于第 $4$ 组测试数据：

• 可以证明不存在满足要求的操作方案。