题目背景

在一个密码学竞赛中，参赛者需要快速计算满足特定数字条件的整数个数。

题目描述

给定正整数 $n$ 和 $k$（$1 \le k \le 9$），求满足以下条件的 $n$ 位非负整数的个数：

• 没有前导零（$0$ 是合法的一位数）。
• 数位中数字 $k$ 出现的次数为偶数（包括 $0$ 次）。

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

输入格式

第一行一个正整数 $t$，表示测试组数。

接下来 $t$ 行，每行两个整数 $n, k$。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例

2
2 3
11 4

73
842367440

提示

样例 1 解释

当 $n=2, k=3$ 时，满足条件的数有 $73$ 个，包括 $10 \sim 12$、$14 \sim 22$ 等（不含数字 $3$），以及 $33$（含两个 $3$）。

数据规模与约定

本题采用捆绑测试。

• 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$。