#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

#define ll int

int main() {
    ios_base::sync_with_stdio();
    cin.tie(0), cout.tie(0);
    ll tt;
    cin>>tt;
    for(ll ij=0;ij<tt;ij++){
        ll n,m;
        cin>>n>>m;
        vector<ll>s(m);
        for(ll i=0 ;  i < m;i++){
            cin>>s[i];
        }
        unordered_map<ll,unordered_map<ll,bool>>dp,pref;
        dp[0][0]=true;
        ll MX=500000;
        for(ll i=1 ; i<= m; i ++){
            ll cnt=0;
            for(auto el : dp){
                for(auto to: el.second){
                    if(to.second){
                        cnt++;
                        pref[-el.first+s[i-1]][to.first]=true;
                        pref[el.first][-to.first + s[i-1]]=true;
                    }
                    if(cnt>=MX){
                        break;
                    }
                }
                if(cnt>=MX){
                    break;
                }
            }
            dp=pref;
            pref.clear();
        }
        ll mx=-1e9;
        for(auto el : dp){
            for(auto to: el.second){
                if(to.second){
                    mx=max(mx,el.first+to.first);
                }
            }
        }
        cout<<mx<<endl;
    }
}
