Problem Statement

We have a red bag, a blue bag, and $N$ card packs. Initially, both bags are empty. Each card pack contains two cards with integers written on them. We know that the $i$-th card pack contains a card with $a_i$ and another with $b_i$.

For each card pack, we will put one of its cards in the red bag, and the other in the blue bag.

After we put all cards in the bags, let $X$ be the greatest common divisor of all integers written on cards in the red bag. Similarly, let $Y$ be the greatest common divisor of all integers written on cards in the blue bag. Our score will be the least common multiple of $X$ and $Y$.

Find the maximum possible score.

Constraints

• All values in input are integers.
• $1 \leq N \leq 50$
• $1 \leq a_i, b_i \leq 10^9$

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
\vdots
a_N b_N

Output

Print the maximum possible score.