King Bajtur, the ruler of Bajtocia, is dreaming about conquering Bitocja. In his dream, just as in the real world, he is still far from defeating his opponent. Therefore, he wonders what he can do to weaken the enemy state.

In his dream, Bitocja consists of $n$ cities (numbered from 1 to $n$) connected by $n-1$ bidirectional roads in such a way that it is possible to travel between any pair of cities using only these roads. In other words, the map of Bitocja forms a tree. However, Bajtur does not remember the exact road network of Bitocja. His brain has therefore generated a random network of roads.

The ruler concluded that it would be a good idea to force the division of Bitocja into $k$ smaller states. By a division, Bajtur means the secret destruction of exactly $k-1$ roads, which will force Bitocja to break into $k$ states, which are the connected components of the graph formed after removing the selected edges.

However, it is not enough for the king to destroy just any $k-1$ roads. Each city in Bitocja has a military coefficient equal to $a_i$ — also randomly generated by Bajtur's brain. Bajtur knows that the stronger a state is militarily, the greater the threat to Bajtocja. Specifically: if the sum of the military coefficients of the cities belonging to a given state is $S$, then the threat posed by this state is equal to $S^2$. The total threat to Bajtocja is equal to the sum of the threats posed by each of the $k$ created states.

Now Bajtur has turned to you — his dreamed (literally!) programmer. Help him and calculate the minimum total threat that Bitocja can pose after being divided into states. Since Bajtur has not yet decided on the value of the parameter $k$, calculate the results for all $k$ from 1 to $n$ inclusive.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10$) denoting the number of Bajtur's dreams (test cases). The following lines contain the description of consecutive test cases; each of them is in the same format.

The first line of the description of a test case contains a single integer $n$ ($2 \le n \le 300$). The second line contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$). The next $n-1$ lines contain the description of the roads of Bitocja; the $i$-th line contains two integers $b_i$ and $c_i$ ($1 \le b_i, c_i \le n$) denoting the road connecting cities numbered $b_i$ and $c_i$. The graph described in each test case is a tree.

Bajtur generated the tests by manually choosing the number $t$ ($1 \le t \le 10$), the range of integers $[n_{\min}, n_{\max}]$ ($2 \le n_{\min} \le n_{\max} \le 300$), and the value $a_{\max}$ ($1 \le a_{\max} \le 10^6$). Then, each test case was generated by him independently in the following way:

• The number of cities $n$ is chosen randomly and uniformly from the range $[n_{\min}, n_{\max}]$.
• Each number $a_1, a_2, \dots, a_n$ is drawn independently and uniformly from the range $[1, a_{\max}]$.
• A sequence of natural numbers $(p_1, p_2, \dots, p_{n-2})$ is generated; each element of the sequence is drawn independently and uniformly from the range $[1, n]$. Bajtur takes as the connection network the tree whose Prüfer sequence is equal to $(p_1, p_2, \dots, p_{n-2})$.

In the Files section of the SIO2 system, you can find an example test generator for this task. The generator takes as its input, in order: the generator seed and the numbers $t, n_{\min}, n_{\max}, a_{\max}$. All tests for this task will be generated with code equivalent to it (i.e., with a different pseudorandom number library, independent of the compiler implementation).

To ensure the randomness of the tests, for each test, the values $t, n_{\min}, n_{\max}, a_{\max}$ were chosen manually, and the generator seed was chosen randomly.

Output

The output should contain $t$ lines describing the answers to consecutive test cases. The answer to each test case should be on a separate line and contain $n$ integers (where $n$ is the number of cities in the given test case); the $k$-th of these numbers should denote the minimum threat that Bitocja can pose after being divided into $k$ states.

Examples

Input 1

2
7
9 1 4 2 6 4 7
1 7
6 4
2 3
5 7
3 4
5 3
5
4 8 2 3 1
4 3
3 1
4 2
5 1

Output 1

1089 545 371 287 227 211 203
324 164 114 102 94

Note

The above test was generated by the code available in the Files section of the SIO2 system using a trial run, for seed 8 122 020 and parameters $t = 2, n_{\min} = 5, n_{\max} = 7, a_{\max} = 10$.

For the first test case, the first printed number is $(9+1+4+2+6+4+7)^2 = 1089$ and represents the total threat posed by the undivided Bitocja. The second printed number corresponds to the total threat in the case of destroying the road connecting cities 5 and 7; in this situation, the threat will be $(9 + 7)^2 + (1 + 4 + 2 + 6 + 4)^2 = 545$.