#include <bits/stdc++.h>
#define pb push_back

using namespace std;
using vi = vector<int>;

const int INF = 1e9;
int N;


void solve() {
    int n, m;
    cin >> n >> m;    

    vi x(m);

    for (int i = 0; i < m; ++i) cin >> x[i];
    // cout << "q" << endl;

    N = 0;

    for (int xx : x) N += abs(xx);

    vector<vi> dpMin(2, vi(2 * N + 1, INF));
    vector<vi> dpMax(2, vi(2 * N + 1, -INF));

    dpMin[1][N] = 0;
    dpMax[1][N] = 0;
    for (int i = 0; i < m; ++i) {
        // cout << "i " << i << endl;
        int ic = (i & 1);
        int ip = (ic ^ 1);

        for (int j = 0; j <= 2 * N; ++j) {
            dpMin[ic][j] = INF;
            dpMax[ic][j] = -INF; 
        }

        for (int aa = 0; aa <= 2 * N; ++aa) {
        //     // cout << "a " << aa << endl;
            int a = aa - N;

            if (dpMin[ip][aa] != INF) {
                // cout << "t " << endl; 
                int b = dpMin[ip][aa];

                int bb = b + N;


                int nb = x[i] - b;
                int na = x[i] - a;

                int naa = na + N;
                int nbb = nb + N;

                // if (i == 6) cout << ' ' << ic << ' ' << aa << ' ' << bb << ' ' << naa << ' ' << nbb << endl;

                // if (b == 800) cout << "c " << i << ' ' << a  << ' ' << b << ' ' << x[i] << endl;
 
                dpMin[ic][naa] = min(dpMin[ic][naa], b);
                dpMin[ic][nbb] = min(dpMin[ic][nbb], a);
                dpMin[ic][aa] = min(dpMin[ic][aa], nb);
                dpMin[ic][bb] = min(dpMin[ic][bb], na);

                dpMax[ic][naa] = max(dpMax[ic][naa], b);
                dpMax[ic][nbb] = max(dpMax[ic][nbb], a);
                dpMax[ic][aa] = max(dpMax[ic][aa], nb);
                dpMax[ic][bb] = max(dpMax[ic][bb], na);
            }

            if (dpMax[ip][aa] != -INF) {
                // cout << "f " << endl;
                int b = dpMax[ip][aa];

                int bb = b + N;


                int nb = x[i] - b;
                int na = x[i] - a;

                int naa = na + N;
                int nbb = nb + N;

                dpMin[ic][naa] = min(dpMin[ic][naa], b);
                dpMin[ic][nbb] = min(dpMin[ic][nbb], a);
                dpMin[ic][aa] = min(dpMin[ic][aa], nb);
                dpMin[ic][bb] = min(dpMin[ic][bb], na);

                dpMax[ic][naa] = max(dpMax[ic][naa], b);
                dpMax[ic][nbb] = max(dpMax[ic][nbb], a);
                dpMax[ic][aa] = max(dpMax[ic][aa], nb);
                dpMax[ic][bb] = max(dpMax[ic][bb], na);      
            }
        }
    }

    int ans = -INF;
    // cout << "ans" << endl;
    for (int aa = 0; aa <= 2 * N; ++aa) {
        int a = aa - N;
        int b = dpMax[(m - 1) & 1][aa];

        ans = max(ans, a + b);
    }

    cout << ans << '\n';
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }
}