Problem Description

You are given a set $S=\{1..n\}$. You have to do the following operations until there are no more than $k$ elements left in the $S$:

Firstly, delete the smallest element of $S$, and then randomly delete another $k$ elements one by one from the elements left in $S$ in equal probability.

Note that the order of another deleted $k$ elements matters. That is to say, you delete $p$ after $q$ or delete $q$ after $p$, which are different ways.

For each $i \in [1,n]$, determine the probability of $i$ being left in the $S$.

It can be shown that the answers can be represented by $\frac{P}{Q}$, where $P$ and $Q$ are coprime integers, and print the value of $P \times Q^{-1} \ mod $ $\space 998244353$.

Input

The first line contains the only integer $T(T \in [1,40])$ denoting the number of test cases.

For each test case:

The first line contains two integers $n$ and $k$.

It guarantees that: $n \in [1,5000] ,\ \sum n \in [1,3 \times 10^4],\ k \in [1,5000].$

Output

For each test case, you should output $n$ integers, the $i$-th of them means the probability of $i$ being left in the $S$.

1
5 2

0 499122177 499122177 499122177 499122177