// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever! 
#include <bits/stdc++.h>

using namespace std;

template<typename L, typename R>
auto range(L l, R r) { return views::iota(l,r); }
auto rev=views::reverse;

template<typename T>
_GLIBCXX_ALWAYS_INLINE void chmax(T &a, T b) { a=max(a,b); }
template<typename T>
_GLIBCXX_ALWAYS_INLINE void chmin(T &a, T b) { a=min(a,b); }
int x=0x7fffffff;
#define int long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
int T; cin>>T;
// int T=1;
while (T--) []{
    int n; cin>>n;
    vector<int> a(n);
    for (auto &i: a) cin>>i;
    if (n==1) {
        cout<<a[0]<<'\n';
        return;
    }
    if (n==2) {
        cout<<max({a[0]+a[1],a[0]-a[1],a[1]-a[0]})<<'\n';
        return;
    }
    array<int,2> f{};
    f[0]=a[0]; f[1]=-a[0];
    for (auto i: range(1,n)) {
        decltype(f) g{}; g[0]=g[1]=-1e18;
        chmax(g[0],f[0]+a[i]);
        chmax(g[1],f[0]-a[i]);
        chmax(g[1],f[1]+a[i]);
        chmax(g[1],f[1]-a[i]);
        swap(f,g);
    }
    cout<<f[1]<<'\n';
}();
}