#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

using ll = long long;

void solve() {
    ll n, m;
    cin >> n >> m;
    vector <ll> a(n, 0), x(m);
    for (int i = 0; i < m; ++i) {
        cin >> x[i];
    }
    multiset <ll> s;
    for (auto i : a) {
        s.insert(i);
    }
    cout << a[0] << ' ';
    for (int i = 0; i < m; ++i) {
        if (i > 0)
            cout << x[i] - x[i - 1] << ' ';
        ll t1 = *s.begin(), t2 = *(--s.end());
        if (t2 - x[i] > x[i] - t1 && i != m - 1) {
            s.extract(t2);
            t2 = x[i] - t2;
            s.insert(t2);
         } else {
            s.erase(s.begin());
            t1 = x[i] - t1;
            s.insert(t1);
        }
        /*for (auto j : s) {
            cout << j << ' ';
        }
        cout << '\n';*/
    }
    ll ans = -1e18;
    for (auto i : s) {
        cout << i << ' ';
        ans += i;
    }
    cout << '\n';
    cout << ans;
}

void solve1() {
    ll n, m;
    cin >> n >> m;
    vector <ll> a(n, 0), x(m);
    for (int i = 0; i < m; ++i) {
        cin >> x[i];
    }
    ll ans = -1e18;
    for (int i = 0; i < (1 << m); ++i) {
        a.assign(n, 0);
        for (int j = 0; j < m; ++j) {
            if (i & (1 << j)) {
                a[1] = x[j] - a[1];
            } else {
                a[0] = x[j] - a[0];
            }
        }
        ans = max(ans, a[0] + a[1]);
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll tt = 1;
    cin >> tt;
    while (tt--) {
        solve1();
        cout << endl;
    }
}
