#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t != 0) {
        int n, m;
        cin >> n >> m;
        vector<long long> a(m);
        for (int i = 0; i < m; i++) {
            cin >> a[i];
        }
        if (n == 1) {
            long long ans = 0;
            for (int i = 0; i < m; i++) {
                ans = a[i] - ans;
            }
            cout << ans << "\n";
        } else {
            map<long long, long long> mp;
            vector<int> num;
            for (int i = 0; i < m; i++) {
                mp[a[i]]++;
            }
            for (auto u : mp) {
                num.push_back(u.first);
            }
            int cnt = (int)mp.size();
            long long ans = 0;
            for (int i = 0; i < m; i++) {
                ans = a[i] - ans;
            }
            for (int i = 0; i < (1ll<<cnt); i++) {
            for (int j = 0; j < cnt; j++) {
                if ((i>>j)&1) {
                    mp[num[j]] = 0;
                } else {
                    mp[num[j]] = 1;
                }
            }
            long long x1 = 0, x2 = 0;
            for (int j = 0; j < m; j++) {
                if (mp[a[j]]) {
                    x1 = a[j] - x1;
                } else {
                    x2 = a[j] - x2;
                }
                mp[a[j]] = 1 - mp[a[j]];
            }
            ans = max(ans, x1 + x2);
            for (int j = 0; j < cnt; j++) {
                if ((i>>j)&1) {
                    mp[num[j]] = 1;
                } else {
                    mp[num[j]] = 0;
                }
            }
            x1 = 0, x2 = 0;
            for (int j = 0; j < m; j++) {
                if (mp[a[j]]) {
                    x1 = a[j] - x1;
                } else {
                    x2 = a[j] - x2;
                }
                if (j % 2 == 0) {
                    mp[j] = 1 - mp[j];
                }
            }
            ans = max(ans, x1 + x2);
        }
        cout << ans << "\n";
        }
        t--;
    }
}



