Є дерево з \textbf{N} вершинами. З кожною вершиною \textbf{u} дерева пов'язана його вартість \textbf{c_u}. Визначимо нестабільність дерева з коренем наступним чином: \includegraphics{https://static.e-olymp.com/content/2f/2ff9ca8c715062f78b8a3483f5069f4c63bf6821.jpg} Через \textbf{L_i} позначено рівень вершини \textbf{i} у відношенні до кореня дерева. Корінь завжди меє рівень \textbf{0}. Вам необхідно вибрати у дереві корінь таким чином, щоб мінімізувати значення нестабільності дерева. \InputFile Перший рядок містить кількість тестів \textbf{T}. Перший рядок кожного тесту містить кількість вершин у дереві \textbf{N}. Наступний рядок містить \textbf{N} цілих чисел, відокремлених пропуском, де \textbf{i}-е число є ваптістю \textbf{i}-ої вершини дерева. Кожен з наступних \textbf{N}-\textbf{1} рядків містить два цілих числа \textbf{a} та \textbf{b} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{N}), які описують ребро між вершинами \textbf{a} та \textbf{b}. Відомо, щто \textbf{1} ≤ \textbf{T }≤ \textbf{20}, \textbf{1} ≤ \textbf{N} ≤ \textbf{20000}, \textbf{1} ≤ \textbf{c_i} ≤ \textbf{1000}. \OutputFile Вихідні дані складаються з \textbf{T} рядків. Кожен рядок містить найменше мождиве значення нестабільності дерева для відповідного тесту.