Statement : H. Counting Sort?

H. Counting Sort?

*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$.

Example

Input

6
2 5
2 2
5 6
4 5 1 4 5
7 7
7 6 5 5 6 7 6
11 7
5 8 9 10 11 4 10 11 7 8 11
12 7
12 12 12 12 12 12 12 12 12 12 12 12
5 10
0 0 0 0 1

Output

2 1 2 2 2
2 4 14 60 554 395
2 6 35 627 63856 171611 490235
2 10 83 10495 286935908 71004446 630281080
2 11 132 48996 207819517 474452948 13828302
1 1 0 0 0 0 0 0 0 0

Note

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$.