Cho dãy số nguyên dương gồm ~N~ phần tử ~a_1,a_2,...,a_N.~ Xét các chỉ số ~(i,j,k,t)~ thỏa mãn ~i<j<k<t~ và ~\gcd(a_i,a_j )+\gcd(a_k,a_t)~ là lớn nhất. Hãy tìm giá trị lớn nhất đó.</p>

Input

Dòng đầu gồm một số nguyên dương ~N~ với ~4 \le N \le 10^5~; dòng thứ hai gồm ~N~ phần tử nguyên dương ~a_1,a_2,…,a_N~ với ~a_i \le 10^5.~

Output

Đáp số của bài toán.

Sample input

6
8 12 4 20 30 15 19

Sample output

19

• Subtast 1: ~4<N \le 50;~</li>
• Subtast 2: ~50<N \le 1000;~</li>
• Subtast 3: ~1000<N \le 10^5.~</li>