//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

#define all(x) begin(x), end(x)
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

void solve(){
    ll n, m;
    cin >> n >> m;
    vector<ll> a(m);
    for (auto &x: a) cin >> x;
    vector<vector<pair<ll,ll>>> kk(1002);
    vector<vector<pair<ll,ll>>> kk1(1002);
    kk[500].push_back({-1, 0});
    for (int i=0; i<m; ++i){
        for (int j=0; j<kk.size(); ++j) for (auto &x: kk[j]){
            ll f = a[i] - (j - 500) + 500;
            ll h = x.second;
            for (int k=x.first + 1; k < i; ++k) h = a[k] - h;
            kk1[f].push_back({i, h});
        }
        kk = kk1;
    }
    ll ans = LLONG_MIN;
    for (int j=0; j<1002; ++j) for (auto &x: kk[j]) if (x.first == m-1) ans = max(ans, j - 500 + x.second);
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll t=1;
    cin >> t;
    while (t--) solve(), cout << '\n';
    return 0;
}
