#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <deque>
#include <iomanip>
using namespace std;
using ll = long long;
void solve() {
	ll n, m;
	cin >> n >> m;
	vector<ll> a(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	if (n == 1) {
		ll ans = 0;
		for (int i = 0; i < m; i++) {
			ans = a[i] - ans;
		}
		cout << ans << endl;
		return;
	}
	if (m <= 18) {
		ll ans = 0;
		for (int mask = 0; mask < (1 << m); mask++) {
			ll first = 0;
			ll second = 0;
			for (int bit = 0; bit < m; bit++) {
				if (((mask >> bit) & 1) == 1) {
					first = a[bit] - first;
				}
				else {
					second = a[bit] - second;
				}
			}
			ans = max(ans, first + second);
		}
		cout << ans << endl;
		return;
	}
	vector < map<ll, map<ll, ll>>> dp(m);
	dp[0][0][a[0] - 0] = 1;
	dp[0][a[0] - 0][0] = 1;
	for (int i = 1; i < m; i++) {
		for (auto elem : dp[i - 1]) {
			for (auto el : elem.second) {
				dp[i][a[i] - elem.first][el.first] = 1;
				dp[i][elem.first][a[i] - el.first] = 1;
			}
		}
	}
	ll ans = 0;
	for (auto elem : dp[m - 1]) {
		for (auto el : elem.second) {
			ans = max(ans, elem.first + el.first);
		}
	}
	cout << ans << endl;
}
int main()
{
	ll t;
	cin >> t;
	while (t--) {
		solve();
	}
}

