// Abhay Singh Bhadoria ( _Asb_ ) //
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int a[N], dp[N][N];
int main() {
    ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--) {
        int n;
        cin >> n;
        for(int i = 1; i <= n; ++i) cin >> a[i];
        for(int i = 0; i <= n; ++i) {
            for(int j = 1; i + j <= n; ++j) {
                int k = j + i;
                dp[j][k] = max(dp[j + 1][k] + (n - i) * a[j], dp[j][k - 1] + (n - i) * a[k]);
            }
        }
        cout << dp[1][n] << endl;
    }
}