#include<bits/stdc++.h>
using namespace std;

//{
//#pragma gcc optimize("Ofast,unroll-loops")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
//#define int long long
//#define double long double
#define MP make_pair
#define F first
#define S second
#define MOD 998244353
//}

int N;
vector<int> a;
vector<vector<int>> cg;
vector<vector<long long>> dp;

long long solve(int l, int r)
{
    if (dp[l][r])
        return dp[l][r];

    if (l == r)
        dp[l][r] = -1;
    else if (l + 1 == r)
        if (cg[l][l + 1] > 1)
            dp[l][r] = cg[l][l + 1];
        else
            dp[l][r] = -1;
    else if (l + 2 == r)
        if (cg[l][l + 1] > 1 && cg[l][l + 2] > 1 && cg[l + 1][l + 2] > 1)
            dp[l][r] = cg[l][l + 1] + cg[l + 1][l + 2];
        else
            dp[l][r] = -1;
    else
    {
        long long ret = -1;
        if (cg[l][r] > 1)
        {
            long long t = solve(l + 1, r - 1);
            if (t != -1)
                ret = max(ret, t + cg[l][r]);
        }

        for (int i = l; i + 1 <= r; i++)
            if (cg[i][i + 1] > 1)
            {
                long long ta = 0, tb = 0;
                if (i > l)
                    ta = solve(l, i - 1);
                if (i + 1 < r)
                    tb = solve(i + 2, r);
                if (ta != -1 && tb != -1)
                    ret = max(ret, ta + tb + cg[i][i + 1]);
            }

        for (int i = l + 1; i < r; i++)
            if (cg[l][i] > 1 && cg[l][r] > 1 && cg[i][r] > 1)
            {
                long long ta = 0, tb = 0;
                if (i - 1 > l)
                    ta = solve(l + 1, i - 1);
                if (i + 1 < r)
                    tb = solve(i + 1, r - 1);
                if (ta != -1 && tb != -1)
                    ret = max(ret, ta + tb + cg[l][i] + cg[i][r]);
            }

        for (int i = l + 1; i < r; i++)
        {
            long long ta = solve(l, i - 1), tb = solve(i, r);
            if (ta != -1 && tb != -1)
                ret = max(ret, ta + tb);
        }

        dp[l][r] = ret;
    }
    return dp[l][r];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N, a.resize(N), cg.resize(N), dp.resize(N);
    for (int i = 0; i < N; i++)
        cin >> a[i], cg[i].resize(N), dp[i].resize(N);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cg[i][j] = __gcd(a[i], a[j]);

    cout << solve(0, N - 1) << '\n';

    return 0;
}

//      *****  *****  *   *  *      *****  *   *  *****  *****
//        *   *   *  *   *  *        *    **  *    *    *   *
//       *   *   *  *****  *        *    * * *    *    *****
//   *  *   *   *    *    *        *    *  **    *    *
//  ****   *****    *    *****  *****  *   *    *    *

//     *   *   ***   *   *  **
//    *   *  *   *  *   *  **
//   * * *  *****  *****  **
//  * * *  *   *  *   *
//  * *   *   *  *   *  **