#include <bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define endl '\n'
typedef long long ll;
using namespace std;

const int N = 55;
ll x[N];
const ll I = 1000;

bool dp[2][I * 2 + 5][I * 2 + 5];

void solve2(int m) {
    dp[1][I][I] = 1;

    int u = 1;
    for (int i = 0; i < m; i++) {
        u = 1 - u;

        for (ll a = 0; a <= 2 * I; a++) {
            for (ll b = 0; b <= 2 * I; b++) {

                if (!dp[1 - u][a][b]) continue;

                ll c = (x[i] - (a - I)) + I;

                if (c < 0 || c > 2 * I) cout << 8 / 0;

                dp[u][c][b] = 1;

                c = (x[i] - (b - I)) + I;

                if (c < 0 || c > 2 * I) cout << 8 / 0;

                dp[u][a][c] = 1;

                dp[1 - u][a][b] = 0;
            }
        }

    }

    ll ans = -I;
    for (ll a = 0; a <= 2 * I; a++) {
        for (ll b = 0; b <= 2 * I; b++) {
            if (dp[u][a][b]) ans = max(ans, (a - I) + (b - I));

            dp[u][a][b] = 0;
        }
    }
    cout << ans << endl;
}

void solve() {
    ll n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) cin >> x[i];

    if (n == 2) {
        solve2(m);
        return;
    }
}

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

    int t;
    cin >> t;
    while (t--) solve();
}
