#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 ll INF = 1e18;
const int I = 500;
const int N = 3e5 + 5;
ll x[N];

//int dp[2][I * 2 + 5][I * 2 + 5];
map<pair<int, int>, int> dp[N];

void solve2(int m) {
    dp[0][{0, 0}]= 1;

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

        for (int a = -I; a <= I; a++) {
            for (int b = -I; b <= I; b++) {
                if (!dp[i - 1][{a, b}]) continue;

                int c = x[i - 1] - a;

                dp[i][{c, b}] = 1;

                c = x[i - 1] - b;

                dp[i][{a, c}] = 1;
                //cout << a + I << " " << c << endl;
            }
        }
    }



    ll ans = 0;
    for (ll a = -I; a <= I; a++) {
        for (ll b = -I; b <= I; b++) {
            if (dp[m][{a, b}]) ans = max(ans, a + b );
        }
    }
    cout << ans << endl;
}

void solve() {
    int 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();
}
