Problem G
Greatest Pair

You are given a tree with $n$ vertices. Each edge has a weight, and each vertex has a label. We denote the label of vertex $i$ as $label(i)$.

A simple path from vertex $s$ to vertex $t$ is defined as an ordered sequence of vertices $v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_ k$, where $v_0 = s, v_ k = t$, and all $v_ i$ are unique. For each valid index $i$, $v_ i$ and $v_{i+1}$ are connected directly by an edge. Note that there exists a simple path between every pair of vertices in a tree.

We define:

• $dist(u, v)$ as the sum of the weight of all edges on the simple path from $u$ to $v$.

• $greatness(u, v) = dist(u, v) \cdot gcd(label(u), label(v))$.

Please find the two different vertices $u$ and $v$ with maximum $greatness(u, v)$.

Input

The input contains multiple test cases, each test case is presented as below:

• The first line contains a single integer $n$ $(2 \le n \le 10^5)$. The sum of $n$ among all test cases does not exceed $10^5$.

• The second line contains $n$ integers, the $i$-th integer is $label(i)$ $(1 \le label(i) \le 5 \cdot 10^5)$.

• In the next $n-1$ lines, each line contains three integers $u$, $v$ and $w$ $(1 \le u, v \le n, 1 \le w \le 10^6)$ describing an edge of weight $w$ connecting two vertices $u$ and $v$.

The input ends with a line containing a single $0$ which is not a test case.

Output

For each test case, print a single line containing the maximum value of $greatness(u, v)$.

2
10 10
1 2 10
0

100