Tiết dạy thao giảng chào mừng ngày nhà giáo Việt Nam 20/11 ở lớp của bé Bình An thật thú vị. Tiết học vận dụng tìm ước chung lớn nhất của hai số nguyên, Bình An rất ấn tượng với tiết đó của thầy T. Bé về nhà háo hức kể chuyện lại với anh trai về tiết học ấy.

Theo mô tả của bé Bình An: Thầy T cho \(n\) bạn học sinh trong lớp đứng thành một hàng ngang, mỗi bạn cầm trên tay một số nguyên dương \(a_1,a_2,…,a_n\). Các bạn còn lại sẽ chia thành các đội chơi, mỗi đội chơi gồm 4 bạn. Nhiệm vụ của mỗi bạn trong mỗi đội chơi là phải phối hợp với nhau và cùng tìm ra 4 vị trí \(1 \le i < j < k < l \le n\), sau đó tính \(GCD(a_i,a_j )+ GCD(a_k,a_l )\) \((*)\). Trong đó \(GCD(x,y)\) là ký hiệu tìm ước chung lớn nhất của hai số nguyên dương \(x,y\). Đội chơi nào tìm được kết quả của biểu thức \((*)\) lớn nhất là đội chơi dành chiến thắng.

Yêu cầu:

• Bạn hãy lập trình tìm kết quả lớn nhất của biểu thức \((*)\).

Dữ liệu vào:

• Dòng đầu gồm một số nguyên dương \(n\)
• Dòng thứ hai gồm \(n\) phẩn tử nguyên dương \(a_1,a_2,…,a_n\) \((a_i \le 10^9)\)

Kết quả ra:

• In ra kết quả bài toán là giá trị \(GCD(a_i,a_j)+GCD(a_k,a_l)\) lớn nhất.

Ví dụ

Giải thích

• ví dụ: \((i,j,k,l)\)=\((1,3,5,6)\).

Ràng buộc:

• Subtask1: 50% số test tương ứng \(n \le 50\).
• Subtask2: 50% số test tiếp theo ứng với \(n \le 2000\).