Дерево

Шановний учаснику, ви, напевно, знаєте, що таке дерево. У структурі даних дерево визначається як граф, у якому між будь-якими двома вершинами існує лише один шлях. Розгляньмо просте завдання. Нехай вершини дерева мають вагу, а вага дерева дорівнює сумі ваг усіх його вершин. Потрібно розділити дерево на два піддерева так, щоб різниця між їх вагами була мінімальною.

Вхідні дані

Перший рядок містить кількість тестів T. Кожен тест починається з кількості вершин у дереві N (2 ≤ N ≤ 10000). Далі йдуть N цілих чисел W_i (1 ≤ W_i ≤ 1000) — ваги вершин з номерами від 1 до N.

Потім слідують N-1 рядків, кожен з яких містить два цілі числа A_i і B_i (1 ≤ A_i, B_i ≤ N), що задають ребро дерева.

Вихідні дані

Для кожного тесту виведіть одне ціле число — найменшу різницю ваг.

Приклади