#include <bits/stdc++.h>

using namespace std;

#define int long long
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

const int INF = 1e18;

const int N = 1e5 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int n, a[N], f[N][2][2][2], ans;

signed main() {
  for (int tc = read(); tc; -- tc) {
    n = read(), ans = -INF;
    rep(i, 1, n) a[i] = read();
    rep(i, 2, n) rep(x, 0, 1) rep(y, 0, 1) rep(z, 0, 1) f[i][x][y][z] = -INF;
    f[1][0][0][0] = 0, f[1][1][1][0] = a[1];
    rep(i, 1, n - 1) rep(j, -1, 1) rep(x, 0, 1) rep(y, 0, 1) rep(z, 0, 1) if (max(x, i + 1 & 1 ? y : z) + j <= 1) {
      int nx = max(max(x + j, j), 0ll), ny = i + 1 & 1 ? (max(max(y + j, j), 0ll)) : y, nz = i + 1 & 1 ? z : max(max(z + j, j), 0ll);
      f[i + 1][nx][ny][nz] = max(f[i + 1][nx][ny][nz], f[i][x][y][z] + j * a[i + 1]);
    }
    rep(x, 0, 1) rep(y, 0, 1) rep(z, 0, 1) ans = max(ans, f[n][x][y][z]);
    printf("%lld\n", ans);
  }
  return 0;
}