Cho dãy số nguyên dương gồm ~N~ phần tử ~a_1, a_2, \dots, a_N~.

Yêu cầu: Tìm bộ chỉ số ~(i, j, k, t)~ thỏa mãn:

• ~i < j < k < t~;
• ~GCD(a_i, a_j) + GCD(a_k, a_t)~ đạt giá trị lớn nhất.

Kí hiệu ~GCD(x, y)~ là ước chung lớn nhất của hai số nguyên dương ~x, y~.

Input

• 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, \dots, a_N~ (~a_i \le 10^5~).

Output

• Một số nguyên là giá trị ~GCD(a_i, a_j) + GCD(a_k, a_t)~ lớn nhất tìm được.

Sample Input 1

6
8 12 4 20 30 15

Sample Output 1

19