Choosing Numbers

Time limit2sMemory limit256 MB

Summary

Pick the largest number that shares no prime factor with any other number in the set.

Level: Medium6 of 10
Topics: Number theory, Brute force
Solved: No attempts yet

Problem

You play a game with friends often, and you keep losing. Whoever holds the largest number at the end wins. When a game starts, a set of distinct numbers lies on the table. On your turn you pick one number from the table and take it into your hand. Sometimes a number in your hand has to be thrown away.

While the game runs, every number sits in one of three places: on the table, in some player's hand, or in the discard pile. When a player picks the number $x$ from the table, $x$ is compared with every number $y$ that is not on the table, which includes the other players' hands, your own hand, and the discard pile. If $x$ and $y$ have a common divisor greater than $1$ , both numbers move to the discard pile, and a number already in the discard pile stays there. The game ends once every number has been taken from the table.

Given the numbers on the table, find the number that wins the game for you when you pick it.

Input

Each line of the input describes the starting table of one game. The line begins with $1 \le n \le 1000$ , followed by $n$ distinct positive integers. Each integer is between $2$ and $2 \times 10^9$ , and these are the numbers lying on the table when the game starts. The input holds at most $1000$ games and ends at end of file.

Output

For each game print the number $x$ that guarantees you win when you pick it, one per line. Every game in the input has exactly one such number.

Examples4

Example 1
Input
```
2 4 7
4 4 8 15 16
4 2 3 4 8
```
Expected output
```
7
15
3
```
Example 2
Input
```
1 2
```
Expected output
```
2
```

Example 3

Input

1 2000000000
3 2 2000000000 3
1 1999999973

Expected output

2000000000
3
1999999973

Example 4
Input
```
5 6 10 15 7 11
```
Expected output
```
11
```