You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

有 $n$ 个整数， $a_1, a_2, ..., a_n$。

你最多可以修改其中一个数，也可以不修改。

问操作后，这些数的最大公约数最大是多少。

Format

Input

第一行一个整数 $n$，表示数的个数。

第二行 $n$ 个整数。

Output

一个整数，表示答案。

Samples

3
2 12 8

4

将第一个数修改成4.

Limitation

30%： $a_i \le 10^5$

另有30%: $n \le 1000$

100% $3 \le n \le 10^5$, $1\le a_i \le 10^9$