eolymp
bolt
Try our new interface for solving problems

Tree

Time limit 1 second
Memory limit 256 MiB

Dear contestant, I bet you must know what a tree represent. In data structure, we learn a tree is a graph in which every two nodes have and only have one path. Here comes an easy problem, given a tree with nodes have its weight, the weight of a tree is the sum of the weight of all nodes on it. Now we have a chance to divide the tree into two subtrees, and we want to know the minimum difference between the two subtrees' weight.

Input data

The first line contains a single integer T, indicating the number of test cases. Each test case begins with one integer N(2N10000), indicating the number of tree's nodes. Then N integers W_i (1W_i1000) follow, indicating the weight of nodes from 1 to N.

Then N-1 lines follow, each line contains two integers A_i and B_i (1A_i, B_iN), indicating one edge of the tree.

Output data

For each test case, output one integer, indicating the minimum weight difference.

Examples

Input example #1
2 
2 
1 2 
1 2 
4 
1 2 1 2 
1 2 
1 3 
1 4
Output example #1
1
2
Source 2010 Wuhan University 4th "Eming" Cup Programming Contest