#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <bitset>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <random>

using namespace std;

// random_device rd;
mt19937 rnd(57575757);

int gen(int l, int r) {
    return (rnd() % (r - l + 1)) + l;
}

// #define int long long
using pii = pair<int, int>;

const int lim = 2e6 + 5e5, c = 1e5;

double gen_double() {
    return double(gen(0, c)) / double(c);
}

const int C = 2805;
int from[2 * C][2 * C];
pii ord1[4 * C * C];
pii ord2[4 * C * C];

void solve() {
    int n, m;
    cin >> n >> m;
    // vector<int> a(n, 0);
    vector<int> vq(m);
    for (int i = 0; i < m; i++) {
        cin >> vq[i];
    }
    if (n == 2) {
        for (int i = 0; i < 2 * C; i++) {
            for (int j = 0; j < 2 * C; j++) {
                from[i][j] = -1;
            }
        }
        from[C][C] = 0;
        int sz1 = 0;
        ord1[0] = {0, 0};
        sz1++;
        int sz2 = 0;
        int res = -1e9;
        int tr = 0;
        for (int i = 0; i < m; i++) {
            tr++;
            if (i % 2 == 0) {
                for (int j = 0; j < sz1; j++) {
                    if (from[vq[i] - ord1[j].first + C][ord1[j].second + C] != tr) {
                        from[vq[i] - ord1[j].first + C][ord1[j].second + C] = tr;
                        ord2[sz2++] = {vq[i] - ord1[j].first, ord1[j].second};
                    }
                    if (from[ord1[j].first + C][vq[i] - ord1[j].second + C] != tr) {
                        from[ord1[j].first + C][vq[i] - ord1[j].second + C] = tr;
                        ord2[sz2++] = {ord1[j].first, vq[i] - ord1[j].second};
                    }
                }
                sz1 = 0;
            } else {
                for (int j = 0; j < sz2; j++) {
                    if (from[vq[i] - ord2[j].first + C][ord2[j].second + C] != tr) {
                        from[vq[i] - ord2[j].first + C][ord2[j].second + C] = tr;
                        ord1[sz1++] = {vq[i] - ord2[j].first, ord2[j].second};
                    }
                    if (from[ord2[j].first + C][vq[i] - ord2[j].second + C] != tr) {
                        from[ord2[j].first + C][vq[i] - ord2[j].second + C] = tr;
                        ord1[sz1++] = {ord2[j].first, vq[i] - ord2[j].second};
                    }
                }
                sz2 = 0;
            }
        }
        for (int i = 0; i < 2 * C; i++) {
            for (int j = 0; j < 2 * C; j++) {
                if (from[i][j] == tr) {
                    res = max(res, i + j - 2 * C);
                }
            }
        }
        cout << res << '\n';
        return;
    }
}

/*
4
1 4
1 2 3 4
2 7
10 3 7 1 4 6 3
4 10
103 354 1 227 179 189 142 201 165 140
5 3
-10 11 -4
 */

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        solve();
    }
}
