P17225 [Math×Girl²] Arithmetic Class

 Cirno’s Perfect Arithmetic Classroom is starting~

“Today we will learn how to reduce fractions!” Cirno stands in front of the blackboard with her hands on her hips. “For example, this—” $$\frac{1\bcancel{6}}{\bcancel{6}4}=\frac14$$ Although this method is strictly completely wrong, the result is actually correct. We define this kind of operation—crossing out a continuous and identical substring from both the numerator and the denominator at the same time—as **magic cancellation**. Now you are given a reduced proper fraction $\frac NM$ (guaranteed that $N

The first line contains an integer $T$, the number of test cases. Then there are $T$ lines, each containing three non-negative integers $N,M,K$.

For each test case, output the number of valid fractions modulo $998244353$.

### Sample Explanation **For sample #1**: For the first test case, the $9$ solutions are: $$ \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} $$ For the second test case, a relatively complicated solution is: $$ \frac{1\bcancel{\textcolor{red}{1715481}}4}{3\bcancel{\textcolor{red}{1715481}}79} $$ ### Constraints and Notes **This problem uses bundled tests.** | Subtask | Points | $K\le$ | Special Property | | :---: | :---: | :---: | :---: | | $1$ | $5$ | $5$ | - | | $2$ | $10$ | $10$ | ^ | | $3$ | $15$ | $10^6$ | $N,M