Дано дерево из \(n\) вершин. На каждой вершине дерева записано число; на \(i\)-й вершине записано число \(a_i\).
Определим функцию \(g(x, y)\) как наибольший общий делитель всех чисел, записанных на вершинах на простом пути от вершины \(x\) до вершины \(y\) (включая эти две вершины). Также определим \(dist(x, y)\) как количество вершин на простом пути между \(x\) и \(y\), включая концы пути. \(dist(x, x) = 1\) для каждой вершины \(x\).
Посчитайте максимальное значение \(dist(x, y)\) по всем таким парам вершин, что \(g(x, y) > 1\).
Выходные данные
Если не существует такой пары вершин \(x, y\), что \(g(x, y) > 1\), выведите \(0\). Иначе выведите максимальное значение \(dist(x, y)\) по всем таким парам.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3 4
1 2
2 3
|
1
|
|
2
|
3
2 3 4
1 3
2 3
|
2
|
|
3
|
3
1 1 1
1 2
2 3
|
0
|