//I wrote this code 4 u today
#include <bits/stdc++.h>

template<class t> using vc = std::vector<t>;

#define nd node*
#define pnd pair<nd, nd>

typedef long long ll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    std::sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(std::unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    std::reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

using namespace std;

const int K = 1488;

mt19937 rnd(228);

int32_t main() {
    std::cin.tie(nullptr)->ios_base::sync_with_stdio(false);
#define int ll
    ll t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &i : a) {
            cin >> i;
        }
        vector<int> dp(n + 1, 0);
        a.insert(a.begin(), 0);
        int mx = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= max(1LL, i - K); --j) {
                dp[i] = max(dp[i], dp[j] + (i - j) * (a[i] + a[j]));
            }
            for (int j = 1; j <= K && j < i; ++j) {
                dp[i] = max(dp[i], dp[j] + (i - j) * (a[i] + a[j]));
            }
            for (int c = 0; c < K; ++c) {
                if (i != 1) {
                    int j = rnd() % (i - 1) + 1;
                    dp[i] = max(dp[i], dp[j] + (i - j) * (a[i] + a[j]));
                }
            }
            mx = max(mx, (n - i) * a[i] + dp[i]);
        }
        cout << mx << "\n";
    }
}