We define a sequence {x}: {x}={x_0, x_1, … , x_n-1 } where x_i is a interger.

We have a function f: {x}->{x’} where {x} is a finite sequence.

After we have a finite sequence {x}, we can get f({x}) follow these rules :

(1). Remove all 0 in x : a 0 b 0 c d 0 e f 0 g => a b c d e f g

(2). Turn 1 into 100 and -1 into -100 : a 1 b 1 -1 c d e f g => a 100 b 100 -100 c d e f g

(3). Add all 2^k (k>1) at the end of the sequence : a 2 b 8 c d e 1024 f g => a 2 b 8 c d e 1024 f g 2 8 1024

(4). Add any positive odd prime x at the end of the sequence x-1 times: a 3 b c 7 d e f 5 g => a 3 b c 7 d e f 5 g 3 3 7 7 7 7 7 7 5 5 5 5

(5). For any positive composite number (not 2^k, k>1 ), we just keep it once: a 6 b 6 c d 6 e 4 4 f g => a 6 b c d e 4 4 f g

(6). Keep any t (t<-1) in the sequence.

For a example:

{x}={-5 1 0 2 9 16 7 5 3 2 9 9 -1}

f({x})={-5 100 2 9 16 7 5 3 2 -100 2 2 16 7 7 7 7 7 7 5 5 5 5 3 3}

We define g({x}) is the sum of all the element in sequence x.

We define h({x}) = g(f({x}))-g({x}).

A consecutive sequence of x is a sequence {x_i, x_i+1, x_i+2, … , x_j} where 0<=i<=j<n.

Now I will give you a sequence {x} .

I want to ask you the maximal h({y}) where {y} is a consecutive sequence of {x}.

Input

One line consists one interger N, the length of {x}.   (N<=10^5, |x_i|<=10000)

Next N lines, each line consists one interger.

Output

The maximal h({y}) where {y} is a consecutive sequence of {x}. ( |h({y})|<=2^63-1 )

Example

Input:
5
1
2
6
6
3
Output:

 101