#include <bits/stdc++.h>

#define ll long long
#define vl vector<ll>
#define pl pair<ll,ll>
#define pb push_back
#define all(x) x.begin(),x.end()

using namespace std;
vl a;
pl maximum(pl a,pl b)
{
	if(a.first+a.second >= b.first+b.second)return a;
	return b;
}
map<vl,pl> seen;
ll n,m;
pl recur(ll s,pl cur)
{
	ll x=cur.first;
	ll y=cur.second;
	if(seen.find({s,x,y})!=seen.end())return seen[{s,x,y}];
	if(s==m)
	{
		return seen[{s,x,y}]=cur;
	}
	ll z=a[s];
	return seen[{s,x,y}]=maximum(recur(s+1,{z-x,y}),recur(s+1,{x,z-y}));
}

void solve()
{
	seen.clear();
	cin>>n>>m;
	a.resize(m);
	for(auto&i:a)cin>>i;
	if(a[0]==a.back())
	{
		cout<<a[0]*(n-(n%2 != m%2))<<endl;
	}
	else
	{
		// -10 * 50 to 10 *50
		// -500 500
		// 1000 * 1000 solution done
		// 5e7 recursive solution
		auto ans=recur(0,{0,0});
		cout<<ans.first+ans.second<<endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	cin>>t;
	while(t--)
	{
		solve();
	}
}