G. Подсчёт GCD
ограничение по времени на тест
4.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$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)$$$ равен этому числу.

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

В первой строке задано целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — количество вершин.

Во второй строке задано $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(1 \le a_i \le 2 \cdot 10^5)$$$ — числа, записанные на вершинах дерева.

Затем следует $$$n - 1$$$ строка, каждая из которых содержит два числа $$$x$$$ и $$$y$$$ $$$(1 \le x, y \le n, x \ne y)$$$, обозначающие ребро между вершиной $$$x$$$ и вершиной $$$y$$$. Гарантируется, что эти ребра задают дерево.

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

Для каждого целого числа $$$i$$$ от $$$1$$$ до $$$2 \cdot 10^5$$$ необходимо сделать следующее: если не существует таких пар $$$(x, y)$$$, что $$$x \le y$$$ и $$$g(x, y) = i$$$, не выводите ничего; иначе выведите два числа: $$$i$$$ и количество описанных пар. Значения $$$i$$$ нужно выводить в возрастающем порядке.

Посмотрите примеры для лучшего понимания.

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