Khoảng cách lớn nhất

Bạn được cho một cây gồm \(n\) đỉnh, mỗi đỉnh được gán một số. Số tại đỉnh \(i\) được ký hiệu là \(a_i\).

Gọi hàm \(g(x, y)\) là ước số chung lớn nhất (GCD) của các số nằm trên đường đi đơn giản từ đỉnh \(x\) đến đỉnh \(y\) (bao gồm cả \(x\) và \(y\)). Đồng thời, định nghĩa \(dist(x, y)\) là số lượng đỉnh trên đường đi đơn giản giữa \(x\) và \(y\), bao gồm cả hai đỉnh \(x\) và \(y\). Lưu ý rằng \(dist(x, x) = 1\) với mọi đỉnh \(x\).

Nhiệm vụ:

• Tìm giá trị lớn nhất của \(dist(x, y)\) trong tất cả các cặp đỉnh \((x, y)\) sao cho \(g(x, y) > 1\).
• Nếu không có cặp đỉnh nào thỏa mãn \(g(x, y) > 1\), in ra \(0\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 2 \cdot 10^5)\) --- số lượng đỉnh trong cây.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq 2 \cdot 10^5)\) --- các số được gán cho các đỉnh.
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) \((1 \leq x, y \leq n, x \neq y)\), biểu diễn một cạnh kết nối hai đỉnh \(x\) và \(y\).

Đảm bảo rằng các cạnh này tạo thành một cây.

Output

• In ra \(0\) nếu không tồn tại cặp đỉnh \((x, y)\) sao cho \(g(x, y) > 1\).
• Ngược lại, in ra giá trị lớn nhất của \(dist(x, y)\) trong tất cả các cặp \((x, y)\) thỏa mãn điều kiện \(g(x, y) > 1\).

Example

3
2 3 4
1 2
2 3

1

3
2 3 4
1 3
2 3

2

Scoring

• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n \leq 100\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(n \leq 2000\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm có \(a_{i} = 2^k\).
• Có \(25\%\) số test tương ứng với \(25\%\) số điểm không có ràng buộc gì thêm.