#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

void solve() {
    ll n, m; cin >> n >> m;
    vector<ll> b(m);
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    ll f = *min_element(b.begin(), b.end());
    ll z = *max_element(b.begin(), b.end());
    f = abs(f);
    ll M = (ll)b.size() * max(f, z);
    vector<int> dp(2 * M + 1, 0), ndp(2 * M + 1, 0);
    vector<vector<int>> rem(2 * M + 1), nrem(2 * M + 1);
    dp[0 + M] = 1;
    rem[0 + M].push_back(b[0]);
    dp[b[0] + M] = 1;
    rem[b[0] + M].push_back(0);
    for (int i = 1; i < m; i++) {
        for (ll s1 = -M; s1 <= M; s1++) {
            if (!dp[s1 + M]) continue;
            for (auto s2 : rem[s1 + M]) {
                ndp[s1 + M] = 1;
                nrem[s1 + M].push_back(b[i] - s2);
                ndp[b[i] - s1 + M] = 1;
                nrem[b[i] - s1 + M].push_back(s2);
            }
        }
        dp = ndp;
        rem = nrem;
        for (ll s1 = -M; s1 <= M; s1++) {
            ndp[s1 + M] = 0;
            if (nrem[s1 + M].size()) {
                nrem[s1 + M].clear();
            }
        }
    }
    ll ans = -INF;
    for (ll s1 = -M; s1 <= M; s1++) {
        if (!dp[s1 + M]) continue;
        for (auto s2 : rem[s1 + M]) {
            ans = max(ans, s1 + s2);
        }
    }
    cout << ans << '\n';
}

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