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)~ 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 tiên gồm một số nguyên dương ~N~;

• Dòng thứ hai gồm ~N~ số 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ị lớn nhất của ~\gcd(a_i, a_j) + \gcd(a_k, a_t)~.

Scoring

Sample Input 1

6
8 12 4 20 30 15

Sample Output 1

19

Notes

Trong ví dụ trên, bộ chỉ số được chọn là ~(i, j, k, t) = (1, 3, 5, 6)~.