Problem Description

There are two matrices $A$ and $B$.

Matrix $A_{n,r}$ has $n$ rows and $r$ columns. Each $A[i][j]\ (1\leq i\leq n,1\leq j\leq r,0\leq A[i][j]\leq m)$ is an integer.

Matrix $B_{r,n}$ has $r$ rows and $n$ columns. Each $B[i][j]\ (1\leq i\leq r,1\leq j\leq n,0\leq B[i][j]\leq m)$ is an integer.

Define $f(x)$ as the number of pair($A_{n,r},B_{r,n}$) satisfying $\displaystyle C=A\times B\ and\ \sum_{i=1}^n\sum_{j=1}^n C[i][j]=x$ .

To simplify the problem, let $r=n^m$.

Now, you need to calculate $f(0),f(1)...f(m)$ $mod$ $998244353$.

Input

The first line contains an integer $T(T \le 15)$. Then $T$ test cases follow.

For each test, input one single line with two integer $n,\ m\in [1,10^5]$.

Output

For each test, output $m+1$ lines. For $i$-th line, print one integer, $f(i-1)$ $mod$ $998244353$.

1
2 1

49
56