Problem C
Dicey Frequencies

Image by Brent Newhall.

You’ve been playing various games that involve rolling several dice, such as Risk, Monopoly, and Yahtzee. There are many games that use dice rolling as the element of chance. You realize that all these games could be significantly changed if you change the number of dice that are rolled (e.g. use three dice instead of two). Further, you could change the game even more by using dice that have different numbers of sides – such as a collection of three dice with $2$ sides, $3$ sides, and $4$ sides respectively. Each die with $s$ sides contains all the values $1$ through $s$, and each side has equal probability.

You want to know the likelihood of getting different sums with different collections of dice, so you need to write a program that will take a description of a set of dice and print out a table of how many ways there are to produce each value with the dice.

For example, if you have the set of three dice described above (with $2$, $3$, and $4$ sides respectively), these dice produce the following values with the associated frequencies (assuming each die is fair, as you should):

For this problem we define the frequency of a sum $x$ as the number of possible ways to roll all the dice so that they add up to $x$.

Input

The input begins with a line containing an integer $1 \le n \le 200$, the number of test cases that follow. Each of the next $n$ lines contains one test case. A test case starts with an integer $1 \le k \le 50$ indicating the number of dice. Following this on the same line are $k$ integers indicating the number of sides on each of the $k$ dice. The number of sides for each die is between $1$ and $100$.

Output

For each test case, let $p$ be the sum of the $n$ dice. Output the frequency for each sum from $1$ to $p$, separated by spaces. The input is chosen so that no frequency is greater than $2^{32}-1$.

3
3 2 4 2
2 4 2
1 10

0 0 1 3 4 4 3 1
0 1 2 2 2 1
1 1 1 1 1 1 1 1 1 1