题目描述

Yuki dreams of reaching the unreachable land. After years of hard work, only this problem remains before her.

Given three integers $a, b, m$. You need to perform $m$ rounds of operations. In the $i$-th round, you can either set $a \leftarrow a \bmod (m - i + 1)$ or choose not to modify $a$. Find the number of ways to make $a = b$ after $m$ rounds, modulo $998244353$.

Two schemes are considered different if and only if there exists some $1 \le i \le m$ such that in one scheme you performed a modification in the $i$-th round, while in the other you did not. Note that choosing to perform $a \leftarrow a \bmod (m - i + 1)$ is considered a modification, regardless of whether the value of $a$ changes after the operation.

You once dreamed of reaching the unreachable land that only exists in fairy tales. Now that Yuki has a chance to realize this dream, you must help her.

输入格式

This problem contains multiple test cases.

The first line contains a positive integer $t$ $(1 \le t \le 10^5)$, representing the number of test cases.

For each test case:

• A single line contains three integers $a, b, m$ $(0 \le b < m \le a \le 2 \cdot 10^5)$.

It is guaranteed that the sum of $a$ over all test cases does not exceed $2 \cdot 10^5$.

输出格式

For each test case, output a single line containing an integer representing the answer modulo $998244353$.

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

25
1
14
0
837481226

提示

For the first test case:

• One valid operation scheme is to perform modifications in the $3$-rd and $4$-th rounds.
• Another valid operation scheme is to perform modifications in all rounds from $1$ to $5$.

For the second test case:

• The only valid operation scheme is to perform a modification in the $3$-rd round.

For the fourth test case:

• It can be proven that no valid operation scheme exists.