Problem Description

You are given two integers $n$,$m$.

Two array $x=\{x_0,x_1,\dots ,x_{l-1}\},y=\{ y_0,y_1,\dots ,\ y_{l-1}\}$ of length $l$ are considered **different** if $x$ couldn't become $ y$ by performing the following operations any number of times:

$\bullet\ $operation 1$:$ Change $x$ to $b$ , for each $i$ $(0\leq i< l), b_i\ =\ (x_i + 1 )\ mod\ m$

$\bullet\ $operation 2$:$ Change $x$ to $b$ , for each $i$ $(0\leq i< l),b_i\ =\ x_{ (i+1)\ mod\ l } $

As an example, if $m=3,\ l=3$, $(0,2,2)$ and $(0,1,0)$ are considered **not different** because $(0,2,2)$ can become $(0,1,0)$ as follows:
$(0,2,2)\stackrel{operation \ 1}{\longrightarrow}(1,0,0)\stackrel{operation \ 2}{\longrightarrow}(0,0,1)\stackrel{operation \ 2}{\longrightarrow}(0,1,0)$

For each $i$ $($$1\leq i\leq n$$)$, find the number of different integer array $a$ of length $i$, satisfied $\forall j \in ( 0,1,\dots ,{i-1} ) , 0\le a_j \le m-1$.

Since the answer may be too large, print it modulo $998244353$.

Input

The first line of the input contains one integer $T$ $($$1\leq T\leq 100$$)$--- the number of test cases. Then $T$ testcases follow.

Each of the next $T$ lines contains two integers $n,m$ $($$1\leq n,m\leq 100000$$)$.

The sum of $n$ over all testcases doesn't exceed $10^{6}$.

Output

For each testcase,output one line contains $n$ integers, separated by space, the $i$-th integer indicating the number of different $a$ of length $i$, modulo $998244353$.

**Don‘t have spaces at the end of the line**

2
10 2
10 100000

1 2 2 4 4 8 10 20 30 56
1 50001 338600275 682529035 345997022 799071125 767573961 525777344 672451750 695859947