Given an array $A$ of $n$ integers. Find the maximum value of $GCD(A_i,A_j)$ with $1 \le i < j \le n$.

Input

• The first line contains an integer $n$.
• The next line contains $n$ integers $A_i$.

Output

• Print the maximum value of $GCD(A_i,A_j)$.

Constraints

• $2 \le n \le 10^5$.
• $1 \le A_i \le 10^6$.

Example

Input:

4
3 6 5 2

Output:

3