I want to end this life impulsively for the decisive time instead of living on the rails that have been laid out for me.

Kashii Moimi & Kaai Yuki, The Decisive Hour

For an array $$$[b_1, b_2, \ldots, b_m]$$$ where $$$0 \le b_i \le m$$$, define $$$f(b)$$$ as an array $$$[c_1, c_2, \ldots, c_m]$$$ such that $$$c_i$$$ is the number of occurrences of $$$i$$$ in the array $$$b$$$.

Define the value $$$g(b)$$$ of an array $$$[b_1, b_2, \ldots, b_m]$$$, where $$$0 \le b_i \le m$$$, as follows:

Initially, there is an empty set $$$S$$$. Create an array $$$d$$$ that is initially equal to $$$b$$$.
Then, you perform the following operation $$$100^{100}$$$ times: Insert $$$d$$$ into $$$S$$$, then set $$$d \gets f(d)$$$.
$$$g(b)$$$ is the number of distinct arrays in $$$S$$$ after the operations.

Now you are given two integers $$$n$$$ and $$$k$$$, as well as an array $$$[r_1, r_2, \ldots, r_n]$$$. For every $$$1\le p\le k$$$, count the number of arrays $$$[a_1, a_2, \ldots, a_n]$$$ where $$$0 \le a_i \le r_i$$$ such that $$$g(a) = p$$$. Since this number may be large, output it modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 50$$$, $$$1 \le k \le 1000$$$).

The second line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$0 \le r_i \le n$$$).

It is guaranteed that the sum of $$$n^3$$$ over all test cases does not exceed $$$50^3$$$.

Output

For each test case, output $$$k$$$ integers — the number of arrays $$$[a_1, a_2, \ldots, a_n]$$$ with $$$0 \le a_i \le r_i$$$ such that $$$g(a) = 1, 2, \ldots, k$$$, respectively.

Print the answer modulo $$$998\,244\,353$$$.

Note

In the first test case, $$$g([0, 0]) = g([1, 0]) = 1$$$, $$$g([0, 1]) = 2$$$, $$$g([2, 0]) = g([0, 2]) = 3$$$, $$$g([1, 1]) = g([2, 2]) = 4$$$, and $$$g([1, 2]) = g([2, 1]) = 5$$$.

In the second test case, $$$f([4, 5, 1, 4, 5]) = [1, 0, 0, 2, 2]$$$, $$$f([1, 0, 0, 2, 2]) = [1, 2, 0, 0, 0]$$$, $$$f([1, 2, 0, 0, 0]) = [1, 1, 0, 0, 0]$$$, $$$f([1, 1, 0, 0, 0]) = [2, 0, 0, 0, 0]$$$, $$$f([2, 0, 0, 0, 0]) = [0, 1, 0, 0, 0]$$$, $$$f([0, 1, 0, 0, 0]) = [1, 0, 0, 0, 0]$$$, $$$f([1, 0, 0, 0, 0]) = [1, 0, 0, 0, 0]$$$. So, $$$g([4, 5, 1, 4, 5]) = 7$$$.

Counting Sort?

Examples