
#include <iostream>
#include <limits>
#include <chrono>
#include <random>
#include <iomanip>
#include <algorithm>
#include <chrono>
#include <random>
#include <math.h>
#include <set>
using namespace std;
#define int long long

void solve() {


	int n, m;
	cin >> n >> m;
	vector <int> vec(m);
	for (int i = 0;i < m;i++)cin >> vec[i];
	if (m == 1) {
		cout << vec[0] << "\n";
		return;
	}
	int M = m;
	m = M / 2;
	int ans = -1e18;
	int min_val = 1e18;
	int max_val = -1e18;
	set <int> val;
	for (int i = 0;i < (1 << m);i++) {
		int b1 = 0, b2 = 0;
		for (int j = 0;j < m;j++) {
			if ((i >> j) & 1) {
				b1 = vec[j] - b1;
			}
			else {
				b2 = vec[j] - b2;
			}
		}
		max_val = max(max_val, b1 + b2);
		min_val = min(min_val, b1 + b2);
	}
	vector <int> buf;
	for (int i = m;i < M;i++)buf.push_back(vec[i]);
	vec = buf;
	m = vec.size();
	for (int i = 0;i < (1 << m);i++) {
		int b1 = 0, b2 = 0;
		int cnt_one = 0;
		for (int j = 0;j < m;j++) {
			if ((i >> j) & 1) {
				cnt_one++;
				b1 = vec[j] - b1;
			}
			else {
				b2 = vec[j] - b2;
			}
		}
		int res = b1 + b2;
		if (cnt_one % 2 == 1) {
			res -= min_val;
		}
		else {
			res += max_val;
		}
		ans = max(res,ans);
	}
	cout << ans << "\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}
