Description

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$.

Input Format

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

Output Format

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

2
2 3
11 4

73
842367440

Hint

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