4034：X密码

有一个包含$$N$$个数位的正整数$$X$$，且$$X$$的满足以下条件：

2、相邻数位的数字差不大于$$1$$

计算符合条件的$$X$$的个数，结果对$$998244353$$取模。

第一行是一个正整数$$T$$表示有$$T$$组测试数据。

每组案例是一个正整数$$N$$表示数字$$X$$的长度。($$1 \le N \le 2 \times 10^5$$)

保证$$T$$组案例的$$N$$之和不会超过$$2 \times 10^5$$。

针对每种案例，在一行中输出符合条件的$$X$$的个数对$$998244353$$取模的结果。

2

1

2

9

25

TKK寒假赛Round#11

题单#20（动态规划之状态机模型）