#include <iostream>
using namespace std;

/*
 * game - finds the winning moves in the following game.  You are given n
 * integers r1, ..., rn, and the object is to remove all the interior values
 * at minimum cost.  The cost to remove any value ri is the gcd of r(i-1) and
 * r(i+1)
 */

const int SIZE = 100;

struct tabentry
{
	int cost;
	int k;
} table[SIZE][SIZE];

int vals[SIZE];

int gcd(int a, int b)
{
	if(b==0)
		return a;
	else
		return gcd(b, a%b);
}

void output(int i, int j, int n)
{
//cout << i << ',' << j << endl;
	if (j == 2) {
		cout << vals[i] << ',' << vals[(i+1)%n] << ',' << vals[(i+2)%n];
		cout << ", cost = " << gcd(vals[i], vals[(i+2)%n]) << endl;
	}
	else if (j > 2){
		int k = table[i][j].k;
		output(i, k, n);
		output((i+k)%n, j-k, n);
		cout << vals[i] << ' ' << vals[(i+k)%n] << ' ' << vals[(i+j)%n] << ", cost = " << gcd(vals[i], vals[(i+j)%n]) << endl;
	}
}
		
int remove(int vals[], int n, int i)
{
	int j=(i+1)%n;
	while(vals[j] == -1)
		j = (j+1)%n;
	int k=(i-1+n)%n;
	while(vals[k] == -1)
		k = (k-1+n)%n;
	return gcd(vals[j], vals[k]);
}

int best;
int bchoices[SIZE];

void doit(int index, int n, int vals[], int choices[], int score)
{
	if (index==n-2) {
		int i=0, j;
		while(vals[i] == -1)
			i++;
		j=i+1;
		while (vals[j] == -1)
			j++;
		score += gcd(vals[i], vals[j]);
		if (score < best) {
			best = score;
			for(int i=0; i<n; i++)
				bchoices[i] = choices[i];
		}
	}
	else {
		for(int i=0; i<n; i++) {
//cout << index << ',' << i << ',' << score << endl;
			if (vals[i] == -1)
				continue;
			int v = remove(vals, n, i);
			int tmp = vals[i];
			vals[i] = -1;
			choices[index] = i;
			doit(index+1, n, vals, choices, score+v);
			vals[i] = tmp;
		}
	}
}

int main()
{
	int n, icase=0;
while (true) {
	cin >> n;
if (n == 0)
break;
	for(int i=0; i<n; i++) {
		cin >> vals[i];
	}

	int choices[SIZE], score=0;
	best = 100000000;
	doit(0, n, vals, choices, score);
	cout << best << endl;
}
return 0;
}