#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <bitset>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <random>

using namespace std;

// random_device rd;
mt19937 rnd(57575757);

int gen(int l, int r) {
    return (rnd() % (r - l + 1)) + l;
}

// #define int long long
using pii = pair<int, int>;

const int lim = 2e6 + 5e5, c = 1e5;

double gen_double() {
    return double(gen(0, c)) / double(c);
}

void solve() {
    int n, m;
    cin >> n >> m;
    // vector<int> a(n, 0);
    vector<int> vq(m);
    for (int i = 0; i < m; i++) {
        cin >> vq[i];
    }
    if (n == 2) {
        const int C = 1605;
        int from[2 * C][2 * C];
        for (int i = 0; i < 2 * C; i++) {
            for (int j = 0; j < 2 * C; j++) {
                from[i][j] = -1;
            }
        }
        from[C][C] = 0;
        int sz1 = 0;
        pii ord1[4 * C * c];
        ord1[0] = {0, 0};
        sz1++;
        pii ord2[4 * C * C];
        int sz2 = 0;
        int res = -1e9;
        int tr = 0;
        for (int i = 0; i < m; i++) {
            tr++;
            if (i % 2 == 0) {
                for (int j = 0; j < sz1; j++) {
                    if (from[vq[i] - ord1[j].first + C][ord1[j].second + C] != tr) {
                        from[vq[i] - ord1[j].first + C][ord1[j].second + C] = tr;
                        ord2[sz2++] = {vq[i] - ord1[j].first, ord1[j].second};
                    }
                    if (from[ord1[j].first + C][vq[i] - ord1[j].second + C] != tr) {
                        from[ord1[j].first + C][vq[i] - ord1[j].second + C] = tr;
                        ord2[sz2++] = {ord1[j].first + C, vq[i] - ord1[j].second + C};
                    }
                }
                sz1 = 0;
            } else {
                for (int j = 0; j < sz2; j++) {
                    if (from[vq[i] - ord2[j].first + C][ord2[j].second + C] != tr) {
                        from[vq[i] - ord2[j].first + C][ord2[j].second + C] = tr;
                        ord1[sz1++] = {vq[i] - ord2[j].first, ord2[j].second};
                    }
                    if (from[ord2[j].first + C][vq[i] - ord2[j].second + C] != tr) {
                        from[ord2[j].first + C][vq[i] - ord2[j].second + C] = tr;
                        ord1[sz1++] = {ord2[j].first + C, vq[i] - ord2[j].second + C};
                    }
                }
                sz2 = 0;
            }
        }
        for (int i = 0; i < 2 * C; i++) {
            for (int j = 0; j < 2 * C; j++) {
                if (from[i][j] == tr) {
                    res = max(res, i + j - 2 * C);
                }
            }
        }
        cout << res << '\n';
        return;
    }
    int res = -1e9;
    vector<int> a(n);
    vector<int> ord;
    for (int i = 0; i < m; i++) {
        ord.push_back(gen(0, n - 1));
    }
    auto calc_f = [&] () -> int {
        fill(a.begin(), a.end(), 0);
        for (int i = 0; i < m; i++) {
            a[ord[i]] = vq[i] - a[ord[i]];
        }
        int temp = 0;
        for (int i : a) {
            temp += i;
        }
        res = max(res, temp);
        return temp;
    };
//    for (int mask = 0; mask < (1 << m); mask++) {
//        for (int i = 0; i < m; i++) {
//            ord[i] = ((mask >> i) & 1);
//        }
//        calc_f();
//    }
    int fp = calc_f();
    int op = 0;
    double t = 1.0;
    while (op < lim) {
        op++;
        t *= 0.987;
        int id = gen(0, m - 1);
        int val = ord[id] ^ 1;
        int old = ord[id];
        ord[id] = val;
        int fn = calc_f();
        t += 0.00002;
        if (fn > fp || gen_double() < 1.3 * exp((fn - fp) / t * 0.2)) {
            fp = fn;
        } else {
            ord[id] = old;
        }
    }
    cout << res << '\n';
}

/*
4
1 4
1 2 3 4
2 7
10 3 7 1 4 6 3
4 10
103 354 1 227 179 189 142 201 165 140
5 3
-10 11 -4
 */

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        solve();
    }
}
