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. \InputFile The first line contains a single integer \textbf{T}, indicating the number of test cases. Each test case begins with one integer \textbf{N}(\textbf{2} ≤ \textbf{N} ≤ \textbf{10000}), indicating the number of tree's nodes. Then \textbf{N} integers \textbf{W_i} (\textbf{1} ≤ \textbf{W_i} ≤ \textbf{1000}) follow, indicating the weight of nodes from \textbf{1} to \textbf{N}. Then \textbf{N-1} lines follow, each line contains two integers \textbf{A_i} and \textbf{B_i} (\textbf{1} ≤ \textbf{A_i}, \textbf{B_i} ≤ \textbf{N}), indicating one edge of the tree. \OutputFile For each test case, output one integer, indicating the minimum weight difference.