Problem Description

To celebrate Children's Day, a mother of $k$ kids comes to the shop to buy sweets. There are $n$ boxes of sweets in the shop, the $i$-th box has $w_i$ sweets. The mother will choose which boxes to buy, and will divide all the bought boxes among the $k$ kids. Each kid will receive several (maybe zero) boxes, and will count the total number of sweets he receives. Assume the $i$-th kid receives $c_i$ sweets, the unfairness is defined as $\sum_{i=1}^k c_i^2$. To make all the kids happy, the mother will always divide boxes to minimize the unfairness. Note that she can not open any box to adjust the number of sweets inside it.

The mother is wondering which boxes to buy. She can not make her final decision. Please write a program to help the mother try all possible $2^n-1$ non-empty subsets of boxes to buy, and figure out the minimum unfairness for each subset. Note that you only need to report the sum of the minimum unfairness among all $2^n-1$ non-empty subsets.

Input

The first line contains a single integer $T$ ($1 \leq T \leq 50$), the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \leq m\leq n \leq 20$, $n+m\leq 23$), denoting the number of boxes and the parameter $m$.

The second line contains $n$ integers $w_1,w_2,\dots,w_n$ ($1\leq w_i\leq 50\,000$), denoting the number of sweets in each box.

It is guaranteed that there are at most $2$ cases such that $n>12$.

Output

For each test case, output $m$ lines, the $i$-th ($1\leq i\leq m$) of which containing an integer, denoting the answer when $k=i$. Note that the answer may be extremely large, so please print it modulo $998\,244\,353$ instead.

1
5 4
1 2 3 4 5

2240
1180
930
884