    #include <bits/stdc++.h>

    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx")

    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    using namespace std;
    template<class T> using oset = tree<T, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;

    //#define int long long
    #define all(a) a.begin(), a.end()
    #define rall(a) a.rbegin(), a.rend()
    int inf = 1e9;
    void solve(){
        int n, m;
        cin >> n >> m;
        vector<int> x(m+1);
        for(int i = 0; i < m; ++i){
            cin >> x[i+1];
        }
        int ans = -inf;
        int c = 16000;
        vector<vector<vector<int>>> dp(2, vector<vector<int>> (2*c+1, vector<int> (2)));
        vector<vector<int>> used(2, vector<int> (2*c+1));
        used[0][c] = 1;
        for(int i = 1; i <= m; ++i){
            int k = x[i];
            for(int val = -c; val <= c; ++val){
                if(!used[1][val]){
                    dp[1][val+c][0] = inf;
                    dp[1][val+c][1] = -inf;
                }
                if(used[0][val+c]){
                    dp[1][val+c][0] = min(dp[1][val+c][0], k - dp[0][val+c][1]);
                    dp[1][val+c][1] = max(dp[1][val+c][1], k - dp[0][val+c][0]);
                    used[1][val+c] = 1;
                }

                if(k-val >= -c && k-val <= c){
                    if(used[0][k-val+c]){
                        dp[1][val+c][0] = min(dp[1][val+c][0], dp[0][k-val+c][0]);
                        dp[1][val+c][1] = max(dp[1][val+c][1], dp[0][k-val+c][1]);
                        used[1][val+c] = 1;
                    }
                }
            }
            swap(dp[1], dp[0]);
            swap(used[1], used[0]);
            for(int val = -c; val <= c; ++val){
                used[1][val+c] = 0;
            }
        }
        for(int val = -c; val <= c; ++val){
            if(used[0][val+c]){
                ans = max(ans, val + dp[0][val+c][1]);
            }
        }
        cout << ans;
    }

    signed main(){
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        int tt = 1;
        cin >> tt;
        while(tt--){
            solve();
            cout << '\n';
        }
        return 0;
    }
