#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t;
    cin >> t;

    while (t--) {
        ll n, m;
        cin >> n >> m;

        vector<ll> x(m);
        for (ll i = 0; i < m; i++) {
            cin >> x[i];
        }

        ll mx = -LONG_LONG_MAX;
        set<ll> st, st1, st2;
        ll mxs = -LONG_LONG_MAX, mns = LONG_LONG_MAX;
        ll mxs1 = -LONG_LONG_MAX, mns1 = LONG_LONG_MAX;
        for (ll i = 0; i < (1 << (m / 2)); i++) {
            ll f = 0, s = 0;
            for (ll b = 0; b < m / 2; b++) {
                if ((i >> b) & 1) {
                    f = x[b] - f;
                } else {
                    s = x[b] - s;
                }
            }
            mxs = max(mxs, f + s);
            mns = min(mns, f + s);
            mxs1 = max(mxs1, f - s);
            mns1 = min(mns1, f - s);
        }

        for (ll i = 0; i < (1 << (m - (m / 2))); i++) {
            ll f = 0, s = 0, cf = 0, cs = 0;
            for (ll b = 0; b < (m - m / 2); b++) {
                if ((i >> b) & 1) {
                    f = x[m / 2 + b] - f;
                    cf++;
                } else {
                    s = x[m / 2 + b] - s;
                    cs++;
                }
            }

            if (cf % 2 && cs % 2) {
                mx = max(mx, f + s - mns);
            } else if (cf % 2) {
                mx = max(mx, f + s - mns1);
            } else if (cs % 2) {
                mx = max(mx, f + s + mns1);
            } else {
                mx = max(mx, f + s + mxs);
            }
        }
        
        cout << mx << '\n';
    }

    return 0;
}
