Problem G
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
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.
Output
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 |
