[hdu5534]DP

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define mset(a, x) memset(a, x, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(b))
#define cas() int T, cas = 0; cin >> T; while (T --)
template<typename T>bool umax(T&a, const T&b){return a<b?(a=b,true):false;}
template<typename T>bool umin(T&a, const T&b){return b<a?(a=b,true):false;}
typedef long long ll;
typedef pair<int, int> pii;

#ifndef ONLINE_JUDGE
    #include "local.h"
#endif

const int N = 2016;

int dp[N][N], f[N];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int n;
    cas() {
        cin >> n;
        for (int i = 1; i < n; i ++) {
            scanf("%d", f + i);
        }
        for (int i = 0; i <= n; i ++) {
            for (int j = 0; j <= n; j ++) {
                dp[i][j] = -1e9 - 7;
            }
        }
        dp[0][0] = f[1] * n;
        for (int i = 0; i < n - 2; i ++) {
            for (int j = 0; j <= i; j ++) {
                umax(dp[i + 1][1], dp[i][j] + f[2] - f[1]);
                umax(dp[i + 1][j + 1], dp[i][j] + f[j + 2] - f[j + 1]);
            }
        }
        int ans = 0;
        for (int i = 0; i <= n - 2; i ++) {
            umax(ans, dp[n - 2][i]);
        }
        cout << ans << endl;
    }
    return 0;
}