#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
// #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define int long long
// #define ll __int128
using namespace std;
// using namespace __gnu_pbds;
// #define unordered_map gp_hash_table
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

const int INF = (int)1e17 + 7;

bool dp[2][1003][1003] = {};
const int MID = 501;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> t(m);
    for (int &i : t) {
        cin >> i;
    }
    dp[0][MID][MID] = true;
    for (int i = 0; i < m; i++) {
        for (int a = 0; a < 1003; a++) {
            for (int b = 0; b < 1003; b++) {
                dp[(i + 1) & 1][a][b] = false;
            }
        }
        for (int a = 0; a < 1003; a++) {
            for (int b = 0; b < 1003; b++) {
                if (!dp[i & 1][a][b]) {
                    continue;
                }
                int r1 = a - MID;
                int r2 = b - MID;
                int z1 = t[i] - r1;
                int z2 = t[i] - r2;
                int new_z1 = z1 + MID;
                int new_z2 = z2 + MID;
                dp[(i + 1) & 1][a][new_z2] = true;
                dp[(i + 1) & 1][new_z1][b] = true;
            }
        }
    }
    int max_res = -INF;
    for (int a = 0; a < 1003; a++) {
        for (int b = 0; b < 1003; b++) {
            if (dp[m & 1][a][b])
                max_res = max(max_res, a + b - 2 * MID);
        }
    }
    cout << max_res << "\n";
}

signed main() {
    // cout << fixed << setprecision(20);
    #ifdef LOCAL
    freopen("C:\\work\\input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #endif
    int t;
    cin >> t;
    while (t--)
    solve();
}