#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast")

#define int long long

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 2e5 + 1;
const int inf = 4e18;

struct node {
    int val = 0, add = 0, idx = -1;

    node() = default;

    node(int _val, int _idx) {
        val = _val;
        idx = _idx;
    }

    node(int _val) {
        val = _val;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i];
    }

    if (n == 1) {
        int ans = 0;
        for (int i = 0; i < m; i++) {
            if (i % 2 == 0) {
                ans += x[i];
            } else {
                ans -= x[i];
            }
        }
        cout << ans * (m % 2 == 0 ? -1 : 1) << '\n';
        return;
    }

    vector<node> t(n * 4);
    vector<node> t1(n * 4);

    function<node(node, node)> combine_min = [&](node a, node b) {
        return node(min(a.val, b.val));
    };

    function<node(node, node)> combine_max = [&](node a, node b) {
        return node(max(a.val, b.val));
    };


    function<void(int, int, int)> build = [&](int v, int l, int r) {
        if (r - l == 1) {
            t[v] = node(x[l]);
            return;
        }
        int m = (l + r) / 2;
        build(v * 2, l, m);
        build(v * 2 + 1, m, r);
        t[v] = combine_min(t[v * 2], t[v * 2 + 1]);
        t1[v] = combine_min(t[v * 2], t[v * 2 + 1]);
    };

    function<void(int, int, int, int, int)> update = [&](int key, int val, int v, int l, int r) {
        if (r - l == 1) {
            t[v] = node(key);
            return;
        }
        int m = (l + r) / 2;
        if (m >= key) {
            update(key, val, v * 2 + 1, m, r);
        } else {
            update(key, val, v * 2, l, m);
        }
        t[v] = combine_min(t[v * 2], t[v * 2 + 1]);
    };

    function<void(int, int, int, int, int)> update1 = [&](int key, int val, int v, int l, int r) {
        if (r - l == 1) {
            t1[v] = node(key);
            return;
        }
        int m = (l + r) / 2;
        if (m >= key) {
            update1(key, val, v * 2 + 1, m, r);
        } else {
            update1(key, val, v * 2, l, m);
        }
        t1[v] = combine_max(t1[v * 2], t1[v * 2 + 1]);
    };

    function<int(int, int, int, int, int)> get_min = [&](int ql, int qr, int v, int l, int r) {
        if (ql >= r or qr <= l) {
            return inf;
        }
        if (ql <= l and qr >= r) {
            return t[v].val;
        }
        int m = (l + r) / 2;
        return min(get_min(ql, qr, v * 2, l, m), get_min(ql, qr, v * 2 + 1, m, r));
    };

    function<int(int, int, int, int, int)> get_max = [&](int ql, int qr, int v, int l, int r) {
        if (ql >= r or qr <= l) {
            return -inf;
        }
        if (ql <= l and qr >= r) {
            return t1[v].val;
        }
        int m = (l + r) / 2;
        return min(get_max(ql, qr, v * 2, l, m), get_max(ql, qr, v * 2 + 1, m, r));
    };
    vector<int> p(m, 1);
    for (int i = 1; i < m; i++) {
        p[i] = p[i - 1] ^ 1;
    }
    vector<vector<int>> a(n);

    function<bool(int)> check = [&](int l) {
        int sm1 = 0, sm2 = x[l];
        for (int i = l; i < m; i++) {
            sm1 += x[i] * (p[i] ? 1 : -1);
        }
        for (int i = l + 1; i < m; i++) {
            sm2 += x[i] * ((p[i] ^ 1) ? 1 : -1);
        }
        return sm2 > sm1;
    };

    for (int i = 0; i < m; i++) {
        if (check(i)) {
            a[1].push_back(x[i]);
            for (int j = i; j < m; j++) {
                p[j] ^= 1;
            }
        } else {
            a[0].push_back(x[i]);
        }
    }
    int ans = 0;
    for (int i = 0; i < 2; i++) {
        int sm = 0;
        for (int j = 0; j < a[i].size(); j++) {
            sm += a[i][j] * (j % 2 == 0 ? 1 : -1);
        }
        ans += sm * (a[i].size() % 2 == 0 ? -1 : 1);
    }
    cout << ans << '\n';
}

signed main() {
#ifdef LOCAL
    freopen("../input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}
