Cho một cây có \(𝑛\) đỉnh, đỉnh thứ \(𝑖\) có hệ số \(a_i\). Với mỗi \(𝑖( i=1,2,…,n)\) mà có tối thiểu một cặp đỉnh thỏa mãn điều kiện sau, hãy in ra \(𝑖\) và số cặp trên một dòng:

• \(𝐺𝐶𝐷\) của hệ số của tất cả các đỉnh trên đường đi đơn giản giữa \(2\) đỉnh đó bằng chính xác \(𝑖\).

Input

• Dòng 1 chứa số nguyên \(n(1≤n≤〖10〗^5)\)

• Dòng 2 chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1 ≤ a_i ≤ 10^5)\)

Output

• Với mỗi \(i\) mà có tối thiểu một cặp đỉnh thỏa điều kiện thì in ra \(i\) và số cặp, \(i=1,2,…,n\)

Input

3
1 2 3
1 2
2 3

Sample Output

1 3

Ràng buộc:

• Subtask 1 : \(n ≤ 100\)

• Subtask 2 : \(n,a_i ≤ 5000\)

• Subtask 1 : Không có ràng buộc gì thêm