Removal Game

Bobby Roberts is totally bored in his algorithms class, so he’s developed a little solitaire game. He writes down a sequence of positive integers and then begins removing them one at a time. The cost of each removal is equal to the greatest common divisor (gcd) of the two surrounding numbers (wrapping around either end if necessary). For example, if the sequence of numbers was $2$, $3$, $4$, $5$ he could remove the $3$ at a cost of $2$ ($= \textrm{gcd}(2,4)$) or he could remove the $4$ at a cost of $1$ ($= \textrm{gcd}(3,5)$). The cost of removing $2$ would be $1$ and the removal of $5$ would cost $2$. Note that if the $4$ is removed first, the removal of the $3$ afterwards now has a cost of only $1$.

Bobby keeps a running total of each removal cost. When he
ends up with just two numbers remaining he takes their gcd,
adds that cost to the running total, and ends the game by
removing them both. The object of the game is to remove all of
the numbers at the minimum total cost. Unfortunately, he spent
so much time in class on this game, he didn’t pay attention to
several important lectures which would lead him to an algorithm
to solve this problem. Since none of you have *ever*
wasted time in your algorithm classes, I’m sure you’ll have no
problem finding the minimum cost given any sequence of
numbers.

Input contains multiple test cases. Each test case consists of a single line starting with an integer $n$ which indicates the number of values in the sequence ($2 \leq n \leq 100$). This is followed by $n$ positive integers which make up the sequence of values in the game. All of these integers will be $\leq 1\, 000$. Input terminates with a line containing a single $0$. There are at most $100$ test cases.

For each test case, display the minimum cost of removing all of the numbers.

Sample Input 1 | Sample Output 1 |
---|---|

4 2 3 4 5 5 14 2 4 6 8 0 |
3 8 |