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∈[1,n], determine the probability of i being left in the S.
It can be shown that the answers can be represented by PQ, where P and Q are coprime integers, and print the value of P×Q−1 mod 998244353.
输入格式
The first line contains the only integer T(T∈[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∈[1,5000], ∑n∈[1,3×104], k∈[1,5000].
输出格式
For each test case, you should output n integers, the i-th of them means the probability of i being left in the S.