#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define lc root<<1
#define rc root<<1|1
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int N = 100010;
int a[N], b[N], ss, tt, n, mn[N*4], sub[N*4];

void up(int root) {
    mn[root] = min(mn[lc], mn[rc]);
}


void build(int root, int l, int r) {
    if (l == r) {
        mn[root] = a[l];
        return;
    }
    int mid=l+r>>1;
    build(lc, l, mid);
    build(rc, mid+1, r);
    up(root);
}

void down(int root) {
    if (sub[root]) {
        sub[lc] += sub[root];
        sub[rc] += sub[root];
        mn[lc] -= sub[root];
        mn[rc] -= sub[root];
        sub[root] = 0;
    }
}

void update(int root, int l, int r, int x, int y, int k) {
    if (x > y) return;
    if (x <= l && y >= r) {
        sub[root] += k;
        mn[root] -= k;
        return;
    }
    int mid = l+r>>1;
    down(root);
    if (x <= mid) update(lc, l, mid, x, y, k);
    if (y > mid) update(rc, mid+1, r, x, y, k);
    up(root);
}

int query(int root, int l, int r, int x, int y) {
    if (x > y) return 1e9;
    if (x <= l && y >= r) {
        return mn[root];
    }
    down(root);
    int mid = l+r>>1, ans = 1e9;
    if (x <= mid) ans = query(lc, l, mid, x, y);
    if (y > mid) ans = min(ans, query(rc, mid+1, r, x, y));
    up(root);
    return ans;
}

int ask(int x) {
    while (tt < n+2 && (b[tt] >= 0|| tt <= x)) tt++;
    if (tt == n+2) return 0;
    int tmp = query(1, 1, n, ss, tt-1);
    if (tmp == 0) {
        ss++;
        return 0;
    }
    return min(tmp, -b[tt]);
}



int main() {
    int T; scanf("%d", &T);
    while (T--) {
        memset(sub, 0, sizeof(sub));
        ll ans = 0;
        scanf("%d", &n);
        rep (i, 1, n) scanf("%d", &a[i]), b[i] = a[i] - a[max(i-2,0)];
        build(1, 1, n);
        
        b[n+1] = -a[n-1], b[n+2] = -a[n];//rep (i, 1, n+2) cout << b[i]<<' ';
        // cout << endl;
        ss = 1, tt = 1;
        while (ss <= n) {
            while (ss < n && (b[ss] <= 0 || b[ss+1] <= 0)) ss++;
            if (ss == n) break;
            int k = min(b[ss], b[ss+1]);
            int num = ask(ss+1);
            int de = min(k, num);
            b[ss] -= de, b[ss+1] -= de;
            b[tt] += de, b[tt+1] += de;
            update(1, 1, n, ss, tt-1, de);
            ans+=de;
        }
        rep (i, 1, n) if (b[i] > 0) ans += b[i];
        cout << ans <<'\n';
    }


    return 0;
}

/*

3
5
2 1 2 1 2
8
1000000000 1000000000 0 1000000000  1000000000 0 1000000000 1000000000

13
1 1 4 5 1 4 1 9 1 9 8 1 0
*/