Given a tree with \textbf{N} nodes. Each node \textbf{u} of the tree has an associated cost \textbf{c_u}. We define the instability of a rooted tree to be: \includegraphics{https://static.e-olymp.com/content/2f/2ff9ca8c715062f78b8a3483f5069f4c63bf6821.jpg} Here \textbf{L_i} is the level of the node \textbf{i} with respect to the root of the tree. Root is assumed to be at level \textbf{0}. You are required to find a root such that minimizes the instability value. \InputFile First line contains an integer \textbf{T}, the number of test cases. Each test case begins with an integer \textbf{N}, the number of nodes in the tree. The next line contains \textbf{N} space separated integers where the \textbf{i}-th integer represents the cost of the \textbf{i}-th node of the tree. The following \textbf{N}-\textbf{1} lines contain two space separated integers \textbf{a} \textbf{b} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{N}) representing an edge between node \textbf{a} and \textbf{b}. It is known that \textbf{1} ≤ \textbf{T }≤ \textbf{20}, \textbf{1} ≤ \textbf{N} ≤ \textbf{20000}, \textbf{1} ≤ \textbf{c_i} ≤ \textbf{1000}. \OutputFile Output \textbf{T} lines. Each line containing the minimum instability value for the corresponding test case.