Koi has a lot of cube blocks, today he wants to build a tower that is both "sturdy" and "good-looking" by stacking them on top of each other.

For the tower to be "sturdy" each of its block must have a volume more than the one above. For the tower to be "good-looking", the volumes of two consecutive blocks must be relatively prime, i.e their greatest common divisor is $1$.

The height of the tower is calculated as the sum of its block's edges.

Given a sequence of positive integers that are the edge length of Koi's blocks, your task is to determine the height of the highest tower satisfy Koi's conditions.

Input

The first line contains an integer $n$ $(1\le n\le 2000)$ - the number of blocks Koi has.

The second line contains $n$ positive integers not exceeding ${10}^9$ - the edges of Koi's blocks.

Output

A single integer - the height of the highest tower Koi wants to build.

Subtask

$30\mathrm{\%}$ of testcases have $n\le 20$.

Example

Input 1:

5
3 6 5 3 1

Output 1:

15

Explaination: Koi can use two blocks $1,3,5,6$ to build the highest tower (of height $1+3+5+6=15$).

Input 2:

4
2 3 6 9

Output 2:

11

Explaination: Koi can use three blocks $2,9$ to build the highest tower (of height $2+9=11$).