B. Dictator Pepe
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The days of jokes are over!

Our beloved leader Pepe has become the supreme leader of Pepeland. As his first great decision, he has decided to eliminate all the noobs and fools from Pepeland. Only the smartest ones may remain!

To find out who is truly smart enough to stay, Pepe decides to create the riddle of the century. For this, he seeks the help of the smartest person on Earth, Woumya.

Pepe takes Woumya to a huge dungeon in Pepeland, where Dali and Sesh are trapped. The dungeon consists of $$$n$$$ rooms connected by $$$n - 1$$$ bidirectional corridors, forming a tree structure (a connected graph with no cycles). Each room has a number written on it, where the number written on room $$$i$$$ is $$$A_i$$$.

A path in the dungeon from room $$$u$$$ to room $$$v$$$ is defined as a sequence of distinct rooms $$$p_1,p_2,\ldots,p_m$$$ such that $$$p_1=u$$$, $$$p_m=v$$$, and $$$p_i$$$ and $$$p_{i+1}$$$ are directly connected by a corridor for all $$$1 \leq i \lt m$$$.

Woumya can choose any path through the dungeon. Suppose the path contains the rooms $$$u_1,u_2,\ldots,u_k$$$ in this order.

The beauty of this path is defined as

$$$$$$ \sum_{i=1}^{k} \gcd(A_{u_1},A_{u_2},\ldots,A_{u_i}). $$$$$$

Woumya wants to impress Pepe by finding the path with the maximum possible beauty. A path containing only a single room is also allowed.

Your task is to calculate the maximum possible beauty.

Input

The input is read from standard input in the following format:

Each test file contains multiple test cases. The first line of the input contains the number of test cases $$$T$$$. Then, for each test case, the input is given in the following format:

  • Line 1: The first line contains an integer $$$n$$$ — the number of rooms in the dungeon.
  • Line 2: The second line contains $$$n$$$ integers $$$A_1,A_2,\ldots,A_n$$$ — the numbers written on the rooms.
  • Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$, meaning that rooms $$$u$$$ and $$$v$$$ are directly connected by a corridor.
Output

For each test case, output a single integer — the maximum possible beauty of any route through the dungeon.

Constraints

  • $$$1 \leq T \leq 10^4$$$.
  • $$$1 \leq n \leq 10^5$$$.
  • $$$1 \leq A_i \leq 10^4$$$ for all $$$1 \leq i \leq n$$$.
  • $$$1 \leq u,v \leq n$$$.
  • It is guaranteed that there exists a unique path between any pair of rooms.
  • The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
Scoring

SubtaskPoints$$$\boldsymbol{n}$$$$$$\boldsymbol{A_i}$$$Additional Constraints
00––The examples
110$$$\le 10^5$$$$$$\le 10^4$$$Every room is directly connected to a room $$$r$$$ by a corridor where $$$1 \le r \le n$$$.
215$$$\le 1000$$$$$$\le 10^4$$$No additional constraints.
375$$$\le 10^5$$$$$$\le 10^4$$$No additional constraints.

Examples
Input
1
4
29 26 19 28
1 2
2 3
3 4
Output
32
Input
1
6
7 10 2 15 9 6
1 2
1 3
1 5
3 4
3 6
Output
18
Input
3
6
4669 9654 8331 3885 9651 7806
1 2
2 3
3 4
4 5
1 6
10
89 23 34 72 41 3 60 99 48 97
1 2
1 3
3 4
4 5
2 6
6 7
3 8
2 9
7 10
4
79 26 19 78
1 2
2 3
3 4
Output
9663
105
82
Note

Example 1

Input


1
4
29 26 19 28
1 2
2 3
3 4

Output


32

Explanation

The optimal path is from room $$$1$$$ to $$$4$$$ where the rooms are $$$1, 2, 3, 4$$$ in order. Hence, the maximum beauty is $$$\gcd(A_1) + \gcd(A_1, A_2) + \gcd(A_1, A_2, A_3) + \gcd(A_1, A_2, A_3, A_4) = \gcd(29) + \gcd(29,26) + \gcd(29,26,19) + \gcd(29,26,19,28) = 32.$$$

Example 2

Input


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

Output


18

Explanation

The optimal path is from room $$$4$$$ to room $$$2$$$, where the rooms are $$$4,3,1,2$$$ in order. Hence, the maximum beauty is

The optimal path is from room $$$4$$$ to $$$2$$$ where the rooms are $$$4, 3, 1, 2$$$ in order. Hence, the maximum beauty is $$$\gcd(A_4) + \gcd(A_4, A_3) + \gcd(A_4. A_3, A_1) + \gcd(A_4, A_3, A_1, A_2)=\gcd (15) + \gcd ( 15, 2) + \gcd(15, 2, 7) + \gcd(15,2,7,10) = 18.$$$