#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long INF = 1e18, MOD = 1e9 + 7;

void solve();

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        int n, m;
        cin >> n >> m;
        vector <int> a(m);
        for (int i = 0; i < m; i++){
            cin >> a[i];
        }
        queue <pair <int, int>> q;
        q.push({0, 0});
        for (int i = 0; i < m; i++){
            vector <vector <bool>> used(801, vector <bool> (801, false));
            queue <pair <int, int>> q1;
            while (!q.empty()){
                auto [x, y] = q.front();
                q.pop();
                int x1 = a[i] - x, y1 = a[i] - y;
                if (!used[x1 + 400][y + 400]){
                    q1.push({x1, y});
                    used[x1 + 400][y + 400] = true;
                }
                if (!used[x + 400][y1 + 400]){
                    q1.push({x, y1});
                    used[x + 400][y1 + 400] = true;
                }
            }
            q = q1;
        }
        int ans = 0;
        while (!q.empty()){
            auto [x, y] = q.front();
            q.pop();
            ans = max(ans, x + y);
        }
        cout << ans << "\n";
    }
}
