You are given a tree T of n nodes. The nodes in the tree are numbered 1 through n. Let's consider some set of different colors numbered 1 through n − 1. Each color costs differently. You are given a sequence cost1, cost2, ..., costn−1 of the color costs.

For each edge, you should choose exactly one color in such a way that no two incident edges have the same color and the sum of the chosen color costs is as minimal as possible.

More formally, let's assign some unique integer from 1 to n − 1 to each of the edges of T. A sequence c1, c2, ..., cn−1 (1 ≤ ck ≤ n − 1) is called an edge coloring of the tree; ck is called the color of the k'th edge. An edge coloring is called valid, if there is no such a pair of edges, that share a common node and have the same color.

The cost of an edge coloring is the sum of the color costs for all the edges of the tree. Your task is to find the cost of the cheapest valid edge coloring.

Input

The first line contains one integer t (1 ≤ t ≤ 16) denoting the number of test cases in the input.

The first line of each test case description contains an integer n (1 ≤ n ≤ 100). The second line contains n − 1 positive integers denoting cost1, cost2, ..., costn−1 (1 ≤ costcolor ≤ 1000). Each of the next n − 1 lines contains two integers u and v denoting an edge of the tree.

Output

For each test case, output a single integer: the cost of the cheapest valid edge coloring.