제거 게임

보비는 알고리즘 수업 시간에 혼자 하는 놀이를 하나 만들었다. 먼저 양의 정수 $n$개를 원형으로 늘어놓는다. 첫 번째 수의 왼쪽 이웃은 마지막 수이고, 마지막 수의 오른쪽 이웃은 첫 번째 수이다.

보비는 수를 하나씩 지운다. 수 하나를 지우는 비용은 그 수의 양옆에 있는 두 수의 최대공약수이고, 수를 지우면 양옆에 있던 두 수가 서로 이웃이 된다.

예를 들어 수열이 $2, 3, 4, 5$이면 $3$을 지우는 비용은 $\gcd(2, 4) = 2$, $4$를 지우는 비용은 $\gcd(3, 5) = 1$, $2$를 지우는 비용은 $\gcd(5, 3) = 1$, $5$를 지우는 비용은 $\gcd(4, 2) = 2$이다. $4$를 먼저 지우면 그다음에 $3$을 지우는 비용은 $\gcd(2, 5) = 1$로 줄어든다.

수가 두 개 남으면 남은 두 수의 최대공약수를 비용에 더하고 두 수를 한꺼번에 지워 게임을 끝낸다.

수열이 주어지면 모든 수를 지우는 데 드는 비용의 합의 최솟값을 구하여라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄이고, 수열의 길이 $n$ ($2 \le n \le 100$)으로 시작해 수열을 이루는 양의 정수 $n$개가 차례로 주어진다. 이 정수는 모두 $1000$ 이하이다.

마지막 줄에는 $0$ 하나만 주어진다. 테스트 케이스는 $1000$개 이하이다.

각 테스트 케이스마다 모든 수를 지우는 최소 비용을 한 줄에 출력한다.