Short Statement Here

You are given an array $A$ of $n$ integers. Find all coprime pairs from $A$. Multiply each of the pairs. Find the maximum among them.

More formally, find MAX$(A_i \cdot A_j)$ where $1 \leq i < j \leq n$ and $gcd(A_i, A_j) = 1$.

Input

Input consists of two lines. First of them consists of an integer $n$ $(2 \leq n \leq 10^{6})$. Second line consists of $n$ integers $A_1, A_2, ..., A_n$ $(1 \leq A_i \leq 10^{6})$

Output

If answer doesn't exist print $-1$. Otherwise, print one integer denoting the answer.

Samples

Input	Output
4 2 8 9 10	90
Coprime pairs are (2,9), (8,9) , (9, 10) and (2 * 9)=18, (8 * 9) = 72, (9 * 10) = 90. Maximum is 90.

Input	Output
4 2 8 10 12	-1
There is no coprime pair.