We define a sequence {x}: {x} = {x₀, x₁ ... x_n-1 } where x_i is an integer.

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 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 integer N, the length of {x}. (N ≤ 10⁵, |x_i| ≤ 10000)

Next N lines, each line consists one integer.

Output

The maximal h({y}) where {y} is a consecutive sequence of {x}. (|h({y})| ≤ 2⁶³-1)

Example

Input:
5
1
2
6
6
3

Output:
101