"Giữa rừng linh mộc, mỗi thân cây mang trong mình năng lượng nguyên thủy. Khi các dòng năng lượng giao hòa, chỉ những đường truyền thuần khiết mới dẫn đến sự cân bằng tuyệt đối của khu rừng."

Tại trung tâm khu rừng cổ, có ~n~ linh mộc được liên kết với nhau bằng ~n-1~ đường rễ ngầm, từ đó tạo thành một mạng cây gồm ~n~ đỉnh. Mỗi linh mộc ~v~ mang trong mình năng lượng nguyên thủy được tính bằng một số nguyên dương ~a_v~. Một đường dẫn năng lượng là dãy các đỉnh liên tiếp (không lặp lại) được nối lại với nhau bằng các đường rễ ngầm giữa hai linh mộc trong cây. Đường dẫn chỉ gồm duy nhất một linh mộc cũng được tính. Ta gọi năng lượng tổng hợp trên đường dẫn ~P~ được tính bằng cách lấy giá trị ước chung lớn nhất của tất cả các linh mộc trên ~P~. Cụ thể hơn, giá trị năng lượng được tính như sau:

$$ ~G(P) = \gcd(a_v : v \in P)~ $$

Một đường dẫn ~P~ được các hiền nhân cho là thuần khiết nếu như ~G(P) = 1~, và họ muốn đếm xem tồn tại bao nhiêu đường dẫn như vậy.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ (~1 \leq n \leq 2 \cdot 10^5~) — số lượng linh mộc trong khu rừng.
Dòng tiếp theo gồm một dãy số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \leq a_v \leq 2 \cdot 10^5~) — lần lượt là năng lượng nguyên thủy của linh mộc ~v~.
Trong ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u_j~ và ~v_j~ — tồn tại rễ ngầm thứ ~j~ được nối giữa hai linh mộc ~u_j~ và ~v_j~.

Output

Gồm một số nguyên duy nhất là số đường dẫn thuần khiết trong khu rừng.

Scoring

Sample Input

5
1 2 3 4 5
1 2
2 3
2 4
1 5

Sample Output

10

Notes

• Các cặp đỉnh mà đường đi giữa chúng thỏa mãn yêu cầu đề bài là: ~(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5)~.