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

struct pt {
  int x, y;

  friend pt operator-(pt a, const pt& b) {
    return {a.x - b.x, a.y - b.y};
  }
};

ll cross(pt a, pt b) {
  return 1ll * a.x * b.y - 1ll * a.y * b.x;
}

ll len(pt a) {
  return 1ll * a.x * a.x + 1ll * a.y * a.y;
}

const int N = 500500;
int n;
pt a[N];

void solve() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i].y;
    a[i].x = i;
  }
  n++;
  a[n] = {0, 0};
  sort(a, a + n, [&] (auto p, auto q) {
    ll c = cross(p, q);
    if (c == 0) {
      return len(p) < len(q);
    }
    return c < 0;
  });
  //for (int i = 0; i < n; i++) {
  //  cerr << a[i].x << ' ' << a[i].y << '\n';
  //}
  vector<int> s;
  s.push_back(0);
  s.push_back(1);
  for (int i = 2; i < n; i++) {
    while (ssize(s) > 1 && cross(a[i] - a[s.back()], a[s.back()] - a[s[ssize(s) - 2]]) < 0) {
      s.pop_back();
    }
    s.push_back(i);
  }
  //for (int i : s) {
  //  cerr << a[i].x << ' ' << a[i].y << '\n';
  //}
  assert(ssize(s) >= 3);
  ll ans = 0;
  for (int i = 2; i < ssize(s); i++) {
    if (a[s[i]].x > a[s[i - 1]].x) {
      ans += 1ll * (a[s[i]].x - a[s[i - 1]].x) * (a[s[i]].y + a[s[i - 1]].y);
    }
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}