There are N integers, A_1, A_2, ..., A_N, written on the blackboard.

You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.

Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Constraints

* All values in input are integers.
* 2 \leq N \leq 10^5
* 1 \leq A_i \leq 10^9

Output

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N

Output

Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.

Examples

Input

3
7 6 8


Output

2


Input

3
12 15 18


Output

6


Input

2
1000000000 1000000000


Output

1000000000
import java.util.*;

public class Main {
	public static void main(String[] args) {
		int i, j;
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int[] a = new int[n];
		for(i=0; i<n; i++) {
			a[i] = Integer.parseInt(sc.next());
		}
		sc.close();
		if(n==2) {
			System.out.println(Math.max(a[0], a[1]));
		} else {
			int[] b = new int[n];
			b[1] = a[0];
			for(i=2; i < n; i++) {
				b[i] = gcd(b[i-1], a[i-1]);
			}
			int[] c = new int[n];
			c[n-2] = a[n-1];
			for(i=n-3; i >= 0; i--) {
				c[i] = gcd(c[i+1], a[i+1]);
			}
			b[0] = c[0];
			c[n-1] = b[n-1];
			int max = 1;
			int pre;
			for(i=0; i < n; i++) {
//				System.out.println("b,c=" + b[i] + "," + c[i]);
				pre = gcd(b[i], c[i]);
				if(pre>max)max=pre;
			}
			System.out.println(max);
		}
	}
	public static int gcd(int a, int b) {
		int t;
		while((t=a%b)!=0) {
			a = b;
			b = t;
		}
		return b;
	}
}
