给定两个整数 $n, m$。

对于两个长度为 $l$ 的数组 $x = \{x_0, x_1, \dots, x_{l-1}\}$ 和 $y = \{y_0, y_1, \dots, y_{l-1}\}$，如果 $x$ 不能通过任意次数执行以下操作变为 $y$，则称它们是不同的：

• 操作 1：将 $x$ 变为 $b$，其中对于每个 $i$ ($0 \le i < l$)，$b_i = (x_i + 1) \pmod m$。
• 操作 2：将 $x$ 变为 $b$，其中对于每个 $i$ ($0 \le i < l$)，$b_i = x_{(i+1) \pmod l}$。

例如，当 $m = 3, l = 3$ 时，$(0, 2, 2)$ 和 $(0, 1, 0)$ 被视为不不同，因为 $(0, 2, 2)$ 可以通过以下方式变为 $(0, 1, 0)$：$(0, 2, 2) \xrightarrow{\text{操作 1}} (1, 0, 0) \xrightarrow{\text{操作 2}} (0, 0, 1) \xrightarrow{\text{操作 2}} (0, 1, 0)$。

对于每个 $i$ ($1 \le i \le n$)，求出长度为 $i$ 且满足 $\forall j \in \{0, 1, \dots, i-1\}, 0 \le a_j \le m-1$ 的不同整数数组 $a$ 的数量。

由于答案可能过大，请输出其对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。 接下来的 $T$ 行中，每行包含两个整数 $n, m$ ($1 \le n, m \le 100000$)。 所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含 $n$ 个整数，用空格分隔，其中第 $i$ 个整数表示长度为 $i$ 的不同数组 $a$ 的数量，对 $998244353$ 取模。

样例

输入格式 1

2
10 2
10 100000

输出格式 1

1 2 2 4 4 8 10 20 30 56
1 50001 338600275 682529035 345997022 799071125 76757396 288545802 858564022 23567920