You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

天海兰太郎被杀后，最原看到图书架后面刷卡器里的尘土并没有消散，陷入了沉思 ……

最原在想，黑幕是如何做到刷卡器的尘土没有消散但是还成功进入了黑幕的房间呢？然后他再次确认了刷卡器，发现了一个密码盘，密码盘下写着一行文字「真正的秘密总是被谎言欺骗，但黑幕不至于欺骗自己」，然后还有一道题，于是最原要用 1min 的时间解出这道题。

题目描述

这道题要求最原构造一个 $n$ 位数，并且满足以下两个要求：

• 「强者从不说废话」，代表着这个数没有前导零，$0$ 没有前导零且是一位数。
• 「强者善于成 $k$ 对合作」，代表着这个数的所有数位中有偶数个 $k$，$0$ 是偶数。

最原很快就让入间制作了一个造数器，但是造数器还需要输入有多少个满足要求的数，于是他就求助于了你，因为做造数器已经用了 59.5s，所以他想让你 0.5s 求出有多少个符合要求的数。

答案对 $998\ 244\ 353$ 取模。

输入格式

本题多测，测试组数为 $t$。
对于每组数据，一行两个整数 $n,k$。

输出格式

对于每组数据，一行一个整数代表答案。

2
2 3
11 4

73
842367440

提示

样例 1 解释

第一组数据，满足要求的数为：

• $0$ 个 $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$ 个 $3$，$33$。

第二组数据的样例解释写了 114514 行，但赛前 0.1s 不小心被黑白熊偷走了，书虫来不及补了。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$n=1$。
• Subtask 2（25 pts）：$n \le 6$。
• Subtask 3（25 pts）：$t \le 100$。
• Subtask 4（45 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le k \le 9$，$1 \le t \le 10^6$。

后续：你用 0.5s 求出了答案，并且答案正确，但是最原将构造出的数输入密码盘发现错误了，所以这件事是一个谎言，最原还要去搜集言弹打学级裁判（