#include <iostream>
#include <set>
#include <vector>
#include <random>
#include <iomanip>
//#include <fstream>
#include <algorithm>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;
#define int long long
const int INF = 1e18;
mt19937 rng(65);
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        vector<int> x(m);
        for (int i = 0; i < m; i++) {
            cin >> x[i];
        }
        int ans = -INF;
        vector<set<vector<int>>> dp(2);
        vector<int> st(n, 0);
        dp[0].insert(st);
        for (int i = 0; i < m; i++) {
            dp[(i + 1) & 1].clear();
            for (auto j : dp[i & 1]) {
                int mnv = INF, idmnv = -1, mxv = -INF, idmxv = -1;
                for (int k = 0; k < n; k++) {
                    if (j[k] > mxv) {
                        mxv = j[k];
                        idmxv = k;
                    }
                    if (j[k] < mnv) {
                        mnv = j[k];
                        idmnv = k;
                    }
                }
                if (i <= 10 or m - i <= 5) {
                    j[idmnv] = x[i] - j[idmnv];
                    dp[(i + 1) & 1].insert(j);
                    j[idmnv] = mnv;
                    j[idmxv] = x[i] - j[idmxv];
                    dp[(i + 1) & 1].insert(j);
                }
                else {
                    if (rng() % 2) {
                        j[idmnv] = x[i] - j[idmnv];
                        dp[(i + 1) & 1].insert(j);
                    }
                    else {
                        j[idmxv] = x[i] - j[idmxv];
                        dp[(i + 1) & 1].insert(j);
                    }
                }

            }
        }
        for (auto j : dp[m & 1]) {
            int sm = 0;
            for (auto i : j) sm += i;
            ans = max(ans, sm);
        }
        cout << ans << '\n';
    }
}