Вам дано дерево на \(n\) вершинах, вершины которого пронумерованы числами от \(1\) до \(n\). На каждом ребре записано некоторое целое число \(w_i\).
Определим \(len(u, v)\) как количество ребер в простом пути между вершинами \(u\) и \(v\), \(gcd(u, v)\) как Наибольший Общий Делитель всех чисел, записанных на ребрах простого пути между вершинами \(u\) и \(v\). Например, \(len(u, u) = 0\) и \(gcd(u, u) = 0\) для любого \(1 \leq u \leq n\).
Вам нужно найти наибольшее значение \(len(u, v) \cdot gcd(u, v)\) по всем парам вершин в дереве.
Выходные данные
Для каждого набора входных данных выведите единственное число равное наибольшему значению \(len(u, v) \cdot gcd(u, v)\) по всем парам вершин в дереве.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 2 1000000000000
4
3 2 6
2 1 10
2 4 6
8
1 2 12
2 3 9
3 4 9
4 5 6
5 6 12
6 7 4
7 8 9
12
1 2 12
2 3 12
2 4 6
2 5 9
5 6 6
1 7 4
4 8 12
8 9 4
8 10 12
2 11 9
7 12 9
|
1000000000000
12
18
24
|