Indra loves a good gamble. So much so, that they gambled away all of their money. Desperate, they have concocted a plan to make some back.

Installed at the centre of town is a Christmas tree which has valuable baubles of various colours. The tree has ~n~ baubles, with bauble ~1~ at the root of the tree, and ~n - 1~ branches which connects one bauble to another. It is known that all baubles are connected to each other via some sequence of branches.

The more baubles of a single colour they have, the more valuable they are. Specifically, if Indra has ~c~ baubles of any one colour, the total value of all of those baubles is ~c^2~.

Indra plans on sneakily cutting a branch and stealing part of the tree to sell the baubles. Specifically, if Indra removes some branch, then they can steal and sell all baubles which are no longer connected to the root. However, they must carefully choose which branch to cut, as stealing more of the tree will likely incur more risk.

To help Indra evaluate their options, for each branch, calculate the value they can gain after cutting that branch.

Hint: A recursive solution may run into stack overflow.

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \le t \le 10^5~). The description of the test cases follows. The first line of each test case contains an integer ~n~ (~2 \le n \le 10^5~), the number of baubles in the Christmas tree. The second line of each test case contains ~n~ integers ~c_i~ (~1 \le c_i \le n~), where ~c_i~ denotes the colour of bauble ~i~. The following ~n - 1~ lines contains two integers ~a, b~, denoting that a branch exists from bauble ~a~ to bauble ~b~.

It is guaranteed that the sum of ~n~ over all testcases is less than or equal to ~10^5~.

Output

For each testcase, output a line containing ~n-1~ integers ~a_i~, where ~a_i~ is the value Indra gains from cutting the ~i~-th branch.

Examples

Input 1

3
7
3 2 3 3 3 2 2
1 3
3 2
2 4
7 2
6 4
5 4
6
3 1 6 5 3 2
6 5
6 1
6 2
1 4
3 1
5
3 2 3 3 1
2 3
5 3
1 3
2 4

Output 1

18 13 5 1 1 1 
1 3 1 1 1 
2 1 6 1