P7158 "dWoi R1" Password of Shady

After Rantaro Amami was killed, Shuichi looked behind the bookshelf and saw that the dust inside the card reader had not dispersed, and fell into deep thought... Shuichi was thinking: how did the mastermind manage to make the dust in the card reader not disperse, yet still successfully enter the mastermind’s room? Then he checked the card reader again and found a password dial. Under the dial there was a line of text: "The real secret is always tricked by lies, but the mastermind would not trick himself." There was also a problem, so Shuichi had to solve it within 1 min.

This problem asks Shuichi to construct an $n$-digit number that satisfies the following two requirements: - "The strong never talk nonsense" means the number has no leading zeros. $0$ has no leading zeros and is a one-digit number. - "The strong are good at forming $k$ pairs to cooperate" means among all digits of this number, there are an even number of digit $k$. $0$ is an even number. Shuichi quickly had Iruma make a number generator, but the generator still needs the count of numbers that satisfy the requirements. So he asked you for help. Since making the generator already took 59.5 s, he wants you to compute how many numbers satisfy the requirements in 0.5 s. Output the answer modulo $998\ 244\ 353$.

**This problem has multiple test cases**, with $t$ test cases. For each test case, one line contains two integers $n, k$.

For each test case, output one integer per line representing the answer.

#### Explanation for Sample 1 For the first test case, the numbers that satisfy the requirements are: - $0$ occurrences of digit $3$: $10 \sim 12$, $14 \sim 22$, $24 \sim 29$, $40 \sim 42$, $44 \sim 52$, $54 \sim 62$, $64 \sim 72$, $74 \sim 82$, $84 \sim 92$, $94 \sim 99$. - $2$ occurrences of digit $3$: $33$. The sample explanation for the second test case had 114514 lines, but 0.1 s before the contest it was accidentally stolen by Monokuma, and the bookworm (shūchóng, 书虫) did not have time to make up for it. #### Constraints and Notes **This problem uses bundled tests.** - Subtask 1 (5 pts): $n=1$. - Subtask 2 (25 pts): $n \le 6$. - Subtask 3 (25 pts): $t \le 100$. - Subtask 4 (45 pts): no special restrictions. For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le k \le 9$, $1 \le t \le 10^6$. --- Postscript: You computed the answer in 0.5 s and it was correct, but when Shuichi entered the constructed number into the password dial, it was wrong. So this was a lie, and Shuichi still has to gather "truth bullets" to fight the class trial ( Translated by ChatGPT 5