#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef long long ll;

void solve();

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1; cin >> tt;
    while (tt--) {
        solve();
        cout << "\n";
    }
}

const ll INF = 1e18;

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

    map<vector<ll>, bool> ok1, ok2;
    vector<ll> kek(n, 0);
    ok1[kek] = 1;

    for (int i = 0; i < m; i++) {
        ok2.clear();
        for (auto [v, _] : ok1) {
            vector<ll> c = v;
            for (int j = 0; j < n; j++) {
                c[j] = a[i] - c[j];
                ok2[c] = 1;
                c[j] = a[i] - c[j];
            }
        }
        ok1 = ok2;
    }

    ll ans = -INF;
    for (auto [v, _] : ok1) {
        ll sum = 0;
        for (auto i : v) sum += i;
        ans = max(ans, sum);
    }
    cout << ans;
}
