#include<bits/stdc++.h>
#pragma GCC target("avx2")
#define int long long
#define F first
#define S second

using namespace std;

const int N = 5e5+10;

bool us[N];

const int C = 501;

bool dp[51][2*C][2*C];

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n, m;
        cin>>n>>m;
        n = min(n, 2ll);
        int p[m+10];
        for(int i = 1; i <= m; i++)
        {
            int x;
            cin>>x;
            p[i] = x;
        }
        if(n == 1)
        {
            int ans = 0;
            for(int i = 1; i <= m; i++)
            {
                if((i%2)) ans += p[i];
                else ans -= p[i];
            }
            cout<<-ans<<"\n";
            continue;
        }
        for(int i = 0; i <= m; i++)
            for(int j = 0; j < 2*C; j++)
                for(int l = 0; l < 2*C; l++)
                    dp[i][j][l] = 0;
        dp[0][C][C] = 1;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 0; j < 2*C; j++)
            {
                for(int l = 0; l < 2*C; l++)
                {
                    dp[i][j][l] |= dp[i-1][p[i]-j+2*C][l];
                    dp[i][j][l] |= dp[i-1][j][p[i]-l+2*C];
                }
            }
        }
        int ans = -1e9;
        for(int j = 0; j < 2*C; j++)
        {
            for(int l = 0; l < 2*C; l++)
            {
                if(dp[m][j][l]) ans = max(ans, l+j-2*C);
            }
        }
        cout<<ans<<"\n";
    }
}

