Yuki 梦想着到达那片无法企及的土地。经过多年的努力，现在她的面前只剩下这道难题了。

给定三个整数 $a, b, m$。你需要进行 $m$ 轮操作。在第 $i$ 轮中，你可以选择将 $a$ 设为 $a \leftarrow a \bmod (m - i + 1)$，或者选择不修改 $a$。求在 $m$ 轮操作后使得 $a = b$ 的方案数，模 $998244353$。

两种方案被认为是不同的，当且仅当存在某个 $1 \le i \le m$，使得在其中一种方案中你在第 $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 \cdot 10^5$)。

保证所有测试用例中 $a$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示模 $998244353$ 后的答案。

样例

输入样例 1

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

输出样例 1

25
1
14
0
837481226

说明

对于第一个测试用例：

• 一种有效的操作方案是在第 3 轮和第 4 轮进行修改。
• 另一种有效的操作方案是在第 1 轮到第 5 轮的所有轮次中都进行修改。

对于第二个测试用例：

• 唯一有效的操作方案是在第 3 轮进行修改。

对于第四个测试用例：

• 可以证明不存在有效的操作方案。