#include <bits/stdc++.h>

#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
mt19937_64 gen;
const ll mod = 1e9 + 7;
const ll INFL = 1e18;
ll binpow(ll a, ll n) {
    if(n == 0) return 1;
    else if(n % 2 == 1) {
        return a * binpow(a, n - 1) % mod;
    } else {
        ll b = binpow(a, n / 2) % mod;
        return b * b % mod;
    }
}
int main()
{
    //seed.time(gen());
    //clock_t start = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll tests; cin >> tests;
    while(tests--) {
        ll n, m; cin >> n >> m;
        vector<ll>a(m + 1);
        for(ll i = 1; i <= m; i++) cin >> a[i];
        //vector<ll>ans(n + 1);
        vector<ll>p(m + 1);
        ll cnt = -1;
        for(ll i = 1; i <= m; i++) {
            cnt++;
            p[i] = 1;
        }
        ld t = 1;
        function<ll(ll, ll)> f = [&](ll in, ll c) {
            p[in] = c;
            vector<ll>res(n + 1, 0);
            for(ll i = 1; i <= m; i++) {
                res[p[i]] = a[i] - res[p[i]];
            }
            ll rs = 0;
            for(ll i = 1; i <= n; i++) rs+=res[i];
            return rs;
        };
        ll ans = f(1, 1);
        ll itr = 2e6;
        while(itr--) {
            //t*=0.99;
            ll ind = (gen() % m) + 1;
            ll c = (gen() % n) + 1;

            ll pr = p[ind];
            ll ans2 = f(ind, c);

            if(ans2 > ans) {
                ans = ans2;
            } /*else {
                ld q2 = (gen() / INFL) % INFL; ld q = exp(ld(abs(ans - ans2)) / ld(t));
                if(q2 < q) {
                    ans = ans2;
                } else {
                    f(ind, pr);
                }
            }*/
        }
        cout << ans << "\n";
    }

    return 0;
}
