#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;
	int best;			// only used for table[*][n-1] entries
} 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)
{
	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 main()
{
	int n, icase=0;
	cin >> n;
	
	while (n > 0)
	{
		for(int i=0; i<n; i++) {
			cin >> vals[i];
		}

		for(int i=0; i<n; i++) {
			table[i][0].cost = 0;
			table[i][0].k = -2;
		}
		for(int i=0; i<n-1; i++) {
			table[i][1].cost = 0;
			table[i][1].k = -2;
		}
		table[n-1][1].cost = 0;
		table[n-1][1].k = -2;
		for(int i=0; i<n; i++){
			table[i][2].cost = gcd(vals[i], vals[(i+2)%n]);
			table[i][2].k = -1;
		}
		for(int len = 3; len<n; len++) {
			for(int i=0; i<n; i++) {
				int best = 100000000;
				int savek;
				for(int k=1; k<len; k++) {
					int tmp = table[i][k].cost + table[(i+k)%n][len-k].cost;
					if (tmp < best) {
						best = tmp;
						savek = k;
					}
				}
				int final = gcd(vals[i], vals[(i+len)%n]);
				if (len == n-1) {
					int tmp = gcd(vals[i], vals[(i+savek)%n]);
					if (tmp < final)
						final = tmp;
					tmp = gcd(vals[(i+savek)%n], vals[(i+len)%n]);
					if (tmp < final)
						final = tmp;
				}
				table[i][len].best = final;
				table[i][len].cost = final + best;
				table[i][len].k = savek;
			}
		}
		if (n == 2)			// these first two cases are kludges
			cout << gcd(vals[0], vals[1]) << endl;
		else if (n==3) {
			int k=0;
			for(int i=1; i<3; i++)
				if (table[i][2].cost < table[k][2].cost)
					k=i;
			cout << 2*table[k][2].cost << endl;
		}
		else {
			int k = 0;
			for(int i=1; i<n; i++) {
				if (table[i][n-1].cost + table[i][n-1].best < table[k][n-1].cost+table[k][n-1].best)
					k = i;
			}
			cout << table[k][n-1].cost +table[k][n-1].best << endl;
		}
		
		cin >> n;
	}
}