// David Poeschl

import java.util.*;

public class RemovalDavid 
{
	static int n;
	
	public static void main(String[] args)
	{		
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		
		while (n != 0)
		{		
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = scan.nextInt();
			//scan.close();
			
			// Memoize the min cost of removing the range from [i, j] inclusive (including wraparound)
			int[][] memo = new int[n][n];

			// Handle single elements
			for (int i = 0; i < n; i++)
				memo[i][i] = gcd(a[b(i - 1)], a[b(i + 1)]);
			
			// Build up to pairs, triples, ...
			for (int length = 1; length < n - 2; length++)
			{
				for (int i = 0; i < n; i++)
				{
					int j = (i + length) % n;
					
					// Consider each element in [i, j] as the final element removed
					
					// Handle the first & last element
					int optimal = Math.min(memo[b(i + 1)][j], memo[i][b(j - 1)]);
					
					// Handle the elements in the middle
					for (int lastRemoved = b(i + 1); lastRemoved != j; lastRemoved = b(lastRemoved + 1))
						optimal = Math.min(optimal, memo[i][b(lastRemoved - 1)] + memo[b(lastRemoved + 1)][j]);
					
					// Regardless of the last element removed, always add the GCD of two elements surrounding [i, j]
					memo[i][j] = optimal + gcd(a[b(i - 1)], a[b(j + 1)]);
				}
			}
			
			int answer = Integer.MAX_VALUE;
			
			// Consider every possible final pair of elements removed
			for (int i = 0; i < n; i++)
				for (int j = i + 1; j < n; j++)
					answer = Math.min(answer, gcd(a[i], a[j]) + memo[b(i + 1)][b(j - 1)] + memo[b(j + 1)][b(i - 1)]);
			
			System.out.println(answer);
			
			n = scan.nextInt();
		}
	}
	
	public static int b(int x)
	{
		return (x + n) % n;
	}
	
	public static int gcd(int a, int b)
	{
		if(b == 0)
			return a;
		else
			return gcd(b, a % b);
	}
}