You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given a tree with N nodes.There are some node has apple. You need to collect of the all apple. In one move you can go any neighbor nodes, it will take exactly one second. You can start from any node and stop any node. Find the minimum numbers of seconds need to collect all available apples in the nodes.

Let's see a figure :

Input

In the first line T, number of test cases.
In each test case,
First line N, the number of the nodes.
Second line an array \(A[]\) and the length of the array is N. If \(A_i\) = 1, that means \(i_{th}\) node has a apple, Otherwise not.
Third line exactly N-1 edges between U and V.

\(1<=T<=10^3\)
\(1<=N<= 2 * 10^5\)
\(A[] = {0,1}\)
\(1<= U,V<=N\)

It is gruantte that sum of N over all test case doesn't exceed \(2 * 10^5\)
Graph is a tree.

Output

In each test cases, print the minimum second required to collect available apple in the tree.
Note : If there is no apple in the tree print 0.

Sample

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

5
0

First test case :