Дано дерево из \(n\) вершин. На каждой вершине дерева записано число; на \(i\)-й вершине записано число \(a_i\).
Определим функцию \(g(x, y)\) как наибольший общий делитель всех чисел, записанных на вершинах на простом пути от вершины \(x\) до вершины \(y\) (включая эти две вершины).
Для каждого целого числа от \(1\) до \(2 \cdot 10^5\) подсчитайте количество таких пар \((x, y)\) \((1 \le x \le y \le n)\), что \(g(x, y)\) равен этому числу.
Выходные данные
Для каждого целого числа \(i\) от \(1\) до \(2 \cdot 10^5\) необходимо сделать следующее: если не существует таких пар \((x, y)\), что \(x \le y\) и \(g(x, y) = i\), не выводите ничего; иначе выведите два числа: \(i\) и количество описанных пар. Значения \(i\) нужно выводить в возрастающем порядке.
Посмотрите примеры для лучшего понимания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
1 2
2 3
|
1 4
2 1
3 1
|
|
2
|
6
1 2 4 8 16 32
1 6
6 3
3 4
4 2
6 5
|
1 6
2 5
4 6
8 1
16 2
32 1
|
|
3
|
4
9 16 144 6
1 3
2 3
4 3
|
1 1
2 1
3 1
6 2
9 2
16 2
144 1
|