#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define int int64_t
#define pw(x) (int64_t(1)<<x)

using namespace std;
using namespace __gnu_pbds;

typedef tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> oset;

mt19937 gen(time(0));

const int INF = 1e18;

const int SIZE = 400 * 800 * 2;

void solve () {
    int n, m;
    cin >> n >> m;
    int x[m];
    for (int i = 0; i < m; ++i) {
        cin >> x[i];
    }
    int MX = 0;
    for (auto to : x) {
        MX = max(MX, abs(to));
    }
    int sum = (MX * m + 1) * 2;
    vector <int> cur;
    cur.pb(0);
    vector <int> mx(sum + 1, -INF), mn(sum + 1, INF);
    vector <int> nmx(sum + 1, -INF), nmn(sum + 1, INF);
    vector <bool> used(sum + 1);
    int C = MX * m;
    mn[C] = 0;
    mx[C] = 0;
    for (int i = 0; i < m; ++i) {
        fill(nmx.begin(), nmx.end(), -INF);
        fill(nmn.begin(), nmn.end(), INF);
        vector <int> add;
        for (auto to : cur) {
            nmx[x[i] - to + C] = max(nmx[x[i] - to + C], mx[to + C]);
            nmx[x[i] - to + C] = max(nmx[x[i] - to + C], mn[to + C]);
            nmn[x[i] - to + C] = min(nmn[x[i] - to + C], mn[to + C]);
            nmn[x[i] - to + C] = min(nmn[x[i] - to + C], mx[to + C]);
            nmx[to + C] = max(nmx[to + C], x[i] - mn[to + C]);
            nmx[to + C] = max(nmx[to + C], x[i] - mx[to + C]);
            nmn[to + C] = min(nmx[to + C], x[i] - mx[to + C]);
            nmn[to + C] = min(nmx[to + C], x[i] - mn[to + C]);
            if (!used[x[i] - to + C]) {
                add.pb(x[i] - to);
                used[x[i] - to + C] = 1;
            }
        }
        for (auto to : add) {
            cur.pb(to);
        }
        add.clear();
        add.shrink_to_fit();
        swap(mx, nmx);
        swap(mn, nmn);
    }
    int ans = -INF;
    for (auto to : cur) {
        ans = max(ans, mx[to + C] + to);
    }
    cout << ans << '\n';
}

int32_t main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // LOCAL
    int q;
    cin >> q;
    while (q--) {
        solve();
    }
}
