P17225 [Math×Girl²] 算术课堂

 **琪露诺的完美算数教室**开课啦~

“今天我们来学约分！”琪露诺在黑板前叉腰，“比如这个——” $$\frac{1\bcancel{6}}{\bcancel{6}4}=\frac14$$ 虽然这个方法严格来说完全错误，但结果居然是对的。 我们定义这种分子分母同时消去一段连续且相同的数为**魔法消除**。 现在给你一个既约真分数 $\frac NM$（保证 $N

输入第一行为一个整数 $T$，表示数据组数。 接下来一共 $T$ 行，每行三个非负整数 $N,M,K$。

对于每组数据，输出方案数对 $998244353$ 取模后的结果。

### 样例解释 **对样例 #1**： 对于第一个数据，$9$ 个解分别为： $$ \frac{26\bcancel{\textcolor{red}{0}}}{37\bcancel{\textcolor{red}{0}}}, \frac{26\bcancel{\textcolor{red}{00}}}{37\bcancel{\textcolor{red}{00}}}, \frac{26\bcancel{\textcolor{red}{000}}}{37\bcancel{\textcolor{red}{000}}}, \frac{26\bcancel{\textcolor{red}{0000}}}{37\bcancel{\textcolor{red}{0000}}}, \frac{26\bcancel{\textcolor{red}{00000}}}{37\bcancel{\textcolor{red}{00000}}}, \frac{26\bcancel{\textcolor{red}{000000}}}{37\bcancel{\textcolor{red}{000000}}}, \frac{2\bcancel{\textcolor{red}{36}}6}{3\bcancel{\textcolor{red}{36}}7}, \frac{2\bcancel{\textcolor{red}{3636}}6}{3\bcancel{\textcolor{red}{3636}}7}, \frac{2\bcancel{\textcolor{red}{363636}}6}{3\bcancel{\textcolor{red}{363636}}7} $$ 对于第二个数据，一个比较复杂的解是： $$ \frac{1\bcancel{\textcolor{red}{1715481}}4}{3\bcancel{\textcolor{red}{1715481}}79} $$ ### 数据范围与约定 **本题开启捆绑测试。** | 子任务 | 分值 | $K\le$ | 特殊性质 | | :---: | :---: | :---: | :---: | | $1$ | $5$ | $5$ | - | | $2$ | $10$ | $10$ | ^ | | $3$ | $15$ | $10^6$ | $N,M