#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

// #pragma GCC target("sse4.2,bmi,bmi2,popcnt,lzcnt,avx2")

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef __int128_t d128;
typedef ll dgt;
typedef pair<dgt, dgt> pdd;
const dgt MOD = 1e9 + 7;
const dgt INF = 1e9 + 1;
const ll INFLL = 1e18 + 1;
const ld EPS = 1e-9;

// typedef tree<dgt, null_type, less<dgt>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define all(x) x.begin(), x.end()

template<typename T1, typename T2>
istream& operator >> (istream&, pair<T1, T2>&);

template<typename T1, typename T2>
ostream& operator << (ostream&, const pair<T1, T2>&);

template<typename T>
istream& operator >> (istream& is, vector<T>& arr) {
    for (T& el: arr)
        is >> el;
    return is;
}

template<typename T>
ostream& operator << (ostream& os, const vector<T>& arr) {
    for (const T& el: arr)
        os << el << ' ';
    return os;
}

template<typename T1, typename T2>
istream& operator >> (istream& is, pair<T1, T2>& pr) {
    return is >> pr.first >> pr.second;
}

template<typename T1, typename T2>
ostream& operator << (ostream& os, const pair<T1, T2>& pr) {
    return os << pr.first << ' ' << pr.second;
}

// const dgt sz = 801;
// typedef array<bitset<sz>, sz> cons;

void solve() {
    dgt n, m;
    cin >> n >> m;
    set<pdd> st;
    st.emplace(0, 0);
    set<pdd> buf;
    for (; m > 0; --m) {
        dgt x;
        cin >> x;
        buf = st;
        st.clear();
        for (pdd pr: buf) {
            st.emplace(pr.first, x - pr.second);
            st.emplace(x - pr.first, pr.second);
        }
    }
    dgt ans = -INFLL;
    for (pdd pr: st)
        ans = max(ans, pr.first + pr.second);
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int reps = 1;
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
#endif
    cin >> reps;
    for (int i = 0; i < reps; ++i) {
#ifdef LOCAL
        cout << "Test case #" << i << " ===========================\n";
#endif
        solve();
#ifdef LOCAL
        cout << "End test ===============================\n";
#endif
    }

    return 0;
}

// g++ -std=c++23 -Wall -Wextra -Wshadow -O2 -DLOCAL -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -fsanitize=address,undefined
