#include <bits/stdc++.h>
#include <bits/extc++.h>

#pragma GCC target("avx2")
#ifndef ABOBA
#pragma GCC optimize("O3")
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll inf = 1e18, mod = 1e9 + 7;

void solve() {
    random_device rd;
    mt19937 rnd(rd());
    ll n, m, ans = 0;
    cin >> n >> m;
    vector<ll> a(m);
    for (auto &i: a) {
        cin >> i;
    }
    for(ll op = 0; op <= ll(1e6) * m; ++op) {
        ll mask = rnd() % (1 << 18), sum = 0;
        vector<ll> b(n);
        for (ll i = 0; i < m; ++i) {
            b[(mask >> i) & 1] = a[i] - b[(mask >> i) & 1];
        }
        for (ll i = 0; i < n; ++i) {
            sum += b[i];
        }
        ans = max(ans, sum);
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll tt = 1;
    cin >> tt;
    while (tt--) solve();
}