题目描述

求有多少个 \(n\) 位无前导零的数满足所有数位中有偶数个 \(k\)。

答案对 \(998244353\) 取模。

格式

输入格式

第一行为测试组数： \(t\)。

对于每组数据，一行两个整数 \(n,k\)。

输出格式

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

样例1

样例输入1

1
2 3

样例输出1

73

样例解释

满足要求的数为：

• \(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\)。

限制

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

测试点编号	\(n\)	\(t\)
\(1\)	\(1\)	无额外限制
\(2,3,4,5,6\)	\(\le 6\)	无额外限制
\(7,8,9,10,11\)	无额外限制	\(t \le 100\)
\(12,13,14,15,16,17,18,19,20\)	无额外限制	无额外限制