#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

#define itn int
#define int long long
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define pii pair<int, int>
#define ff first
#define ss second
#define sz(a) (int)(a).size()
#define ll long long
#define ld long double

mt19937 rnd(time(0));

const int N = 1000;


vector <itn> a, b;

void solve(){
    int n, m;
    cin >> n >> m;
    a.resize(2);
    b.resize(m);
    for (auto &x: b){
        cin >> x;
    }

    unordered_map<int, unordered_map<itn, int>> vsp, vsp1;
    
    vsp1[0][0] = 1;

    for (itn i = 0; i < m; ++i){
        for (auto [j, y]: vsp1){
            for (auto [k, vp]: y){
                vsp[j][b[i] - k] |= vsp1[j][k];
                vsp[b[i] - j][k] |= vsp1[j][k];
            }
        }
        swap(vsp, vsp1);
        vsp.clear();
    }
    int ans = -1e18 - 7;
    for (auto [j, y]: vsp1){
        for (auto [k, vp]: y){
            ans = max(ans, j + k);
        }
    }
    cout << ans << '\n';
}

signed main(){
    cin.tie(nullptr) ->sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t = 1;
    cin >> t;
    while (t--){
        solve();
    }
}