G. Оптимизации из ЧелГУ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево на $$$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)$$$ по всем парам вершин в дереве.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.

Во первой строке каждого набора входных данных дано число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество вершин дерева.

В следующих $$$n-1$$$ строках заданы ребра в формате $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$1 \leq w \leq 10^{12}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное число равное наибольшему значению $$$len(u, v) \cdot gcd(u, v)$$$ по всем парам вершин в дереве.

Пример
Входные данные
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