#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

void fast_in_out() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

#define int long long
#define all(x) (x).begin(), (x).end()
using ll = long long;
using ull = long long;
using ld = long double;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 3e5;
int a[N], n, m;
vector<pair<int, int>> vec, vec1;

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a[i];
    }
    reverse(a, a + m);
    vec = {{0, 0}};
    for (int i = 0; i < m; ++i) {
        vec1.clear();
        for (auto [it, pos]: vec) {
            if (pos >= 2) {
                vec1.back().first = max(vec1.back().first, it - a[i]);
            } else if (pos == 1) {
                vec1.emplace_back(it - a[i], pos - 1);
            }
            if (pos <= n - 1) {
                vec1.emplace_back(it + a[i], pos + 1);
            }
        }
        swap(vec, vec1);
    }
    int ans = -3e14;
    for (auto [it, pos]: vec) {
        if (it < ans) {
            break;
        }
        ans = max(ans, it);
//        cout << it << ' ';
    }
    cout << ans << '\n';
}

signed main() {
    fast_in_out();
    int qwe = 1;
    cin >> qwe;
    while (qwe--) {
        solve();
    }
    return 0;
}
