Buying Snacks

As a foodie, Diana loves eating snacks. One day, her snacks were all confiscated by Bella, so Diana decided to buy some more in a snack shop.

There are totally $n$ different type of snacks in the snack shop, numbered from $1,2,\dots,n$. Each of snacks has two sizes of packages, $big$ ones and $small$ ones. Diana wants to taste different snacks as many as possible, so she will buy $at$ $most$ $1$ $package$ for each type of snacks. For any $two$ $adjacent$ kinds of snacks(no matter the size), Diana can choose to buy them as a bundle, so that she could have a discount compared to buying them respectively. To simplify this problem, we assume that any $small$ package of snacks costs $1$ coin, any $big$ one costs $2$ coins and any discount is $1$ coin. Now Diana wonders how many different ways to buy snacks with $just$ $k$ coins.

Please output the answer module $998244353$ for each $k\in[1,m]$.

Two ways are considered the $same$ if types of snacks, sizes of snacks and bundles are all the same.

$Notice$: For $two$ $adjacent$ kinds of snacks, Diana could either buy them respectively without a discount or buy them as a bundle, and they are considered as different ways.

$For$ $example$: when $n=2,k=2$, there are $5$ different ways:

$(1b), (2b), (1s$&$2b), (1b$&$2s), (1s)(2s)$

(number means the type of snack, $s$ means its a small package, $b$ means its a big package, & means its a bundle)

The first line contains an integer $T(T\leq 5)$ , denoting the number of test cases.

Each test case contains two integers $n(1\leq n \leq 10^9)$, $m(1 \leq m \leq 20000)$ denoting the number of types of snacks and the maximum number of coins.

It is guaranteed that for all test cases, $\sum m \leq 30000$

For each test case, output a line with $m$ integers, indicating the answer.

2

2 3

5 4

3 5 3

9 38 97 166

2021“MINIEYE杯”中国大学生算法设计超级联赛（8）