Password of Shady（简化版）

题目描述

给定两个整数 (n, k)\((1\le k\le 9)\)。我们要统计没有前导零的 (n) 位十进制数中，有偶数个数字 (k) 的有多少个。把答案对 (998244353) 取模。

• "没有前导零"：首位必须是 (\(1\sim 9\))。
• "偶数个 (k)"：数字 (k) 在所有数位中出现的次数是 (\(0,2,4,\dots\))（注意 0 次也算偶数）。

输入格式

• 第一行：测试组数 (t)。
• 接下来 (t) 行：每行两个整数 (n, k)。

输出格式

• 对每组数据，输出一个整数：满足条件的 (n) 位数的个数（模 (998244353)）。

样例

输入

2
2 3
11 4

输出

73
842367440

样例解释(n=2, k=3)

• 有 0 个"3"的两位数（首位不能是 0）：10–12、14–22、24–29、40–42、44–52、54–62、64–72、74–82、84–92、94–99；
• 有 2 个"3"的两位数：33。 合计 73 个。

数据范围

• (\(1 \le n \le 10^5\))
• (\(1 \le k \le 9\))
• (\(1 \le t \le 10^6\))