Description

A sequence has $n$ numbers. We define an operation: we can divide two adjacent numbers simultaneously by one of their common divisors, and the cost of this operation is the value of that divisor. After performing such operations several times, we can transform the original sequence so that every pair of adjacent numbers is coprime. Find the minimum total cost to achieve this.

Input Format

The first line contains a positive integer $n$. In the next $n$ lines, each line contains an integer, representing each number in the sequence in order.

Output Format

Output the minimum cost.

3
3
12
6

5

Hint

• 30% of the testdata satisfies $n \leq 20$.
• 100% of the testdata satisfies $1 \leq n \leq 10000$, and the numbers in the sequence satisfy $1 \leq A_i \leq 2 \times 10^7$.

Translated by ChatGPT 5