Full Path Eraser

 There is a rooted tree of 

N$N$ vertices rooted at vertex 1$1$. Each vertex v$v$ has a value Av$A_v$ associated with it.

You choose a vertex v$v$ (possibly the root) from the tree and remove all vertices on the path from the root to the vertex v$v$, also including v$v$. This will result in a forest of zero or more connected components.

The beauty of a connected component is the GCD$\mathrm{G}\mathrm{C}\mathrm{D}$ of the values of all vertices in the component. Find the maximum value of the sum of beauties of the obtained connected components for any choice of v$v$.

Here, GCD$\mathrm{G}\mathrm{C}\mathrm{D}$ stands for Greatest Common Divisor.

Input Format

• The first line contains a single integer T$T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N$N$ — the size of the tree.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ denoting the values associated with each vertex.
• The next N−1$N-1$ lines contain two space-separated integers u$u$ and v$v$ — denoting an undirected edge between nodes u$u$ and v$v$.

It is guaranteed that the edges given in the input form a tree.

Output Format

For each test case output the maximum value of the sum of beauties of the obtained connected components for any choice of v$v$.

Constraints

• 1≤T≤2⋅104$1\le T\le 2\cdot {10}^4$
• 1≤N≤3⋅105$1\le N\le 3\cdot {10}^5$
• 1≤Ai≤109$1\le A_i\le {10}^9$
• 1≤u,v≤N$1\le u,v\le N$ and u≠v$u\ne v$
• It is guaranteed that the edges given in the input form a tree.
• The sum of N$N$ over all test cases does not exceed 3⋅105$3\cdot {10}^5$

Sample Input 1 

1
10
15 30 15 5 3 15 3 3 5 5
1 2
1 5
2 3
2 4
5 6
5 7
5 8
7 9
7 10

Sample Output 1 

33

Explanation

The tree from the sample is as follows.

If vertex v=7$v=7$ is chosen, vertices 1$1$, 5$5$ and 7$7$ are removed.

The resulting forest contains five connected components {8},{6},{10},{9}$\{8\},\{6\},\{10\},\{9\}$ and {2,3,4}$\{2,3,4\}$.

The beauties of the connected components are 3$3$, 15$15$, 5$5$, 5$5$ and 5$5$ respectively. Thus the answer is 3+15+5+5+5=33$3+15+5+5+5=33$.

It can be shown that this is the maximum value possible for any choice of v$v$.