//#pragma GCC optimize("O2")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target("popcnt") 1's count

#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <unordered_set>
#include <climits> //INT_MAX, LLONG_MAX
#include <random> //mt19937
#include <numeric> //gcd
#include <bitset>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using db = double;
//#define int long long

constexpr ll inf = 2e18;

void sol() {
    ll n, m;
    cin >> n >> m;
    vector <ll> v(m);
    bool flag = true;
    for (int i = 0; i < m; i++) {
        cin >> v[i];
        if (v[i] != v[0]) {
            flag = false;
        }
    }
    if (flag) {
        if (m <= n) {
            cout << m * v[0] << '\n';
        } else {
            if (n % 2 == m % 2) {
                cout << n * v[0] << '\n';
            } else {
                cout << (n - 1) * v[0] << '\n';
            }
        }
    } else if (n == 2) {
//        ll mx = -inf;
//        for (int mask = 0; mask < (1 << m); mask++) {
//            ll m1 = 0, m2 = 0;
//            for (int i = 0; i < m; i++) {
//                if ((mask >> i) & 1) {
//                    m1 = v[i] - m1;
//                } else {
//                    m2 = v[i] - m2;
//                }
//            }
//            mx = max(mx, m1 + m2);
//        }
//        cout << mx << '\n';
        if (m % 2) {
            ll ans = v[m - 1];
            for (int i = 0; i < m - 1; i += 2) {
                if (v[i] >= v[i + 1]) {
                    ans += v[i] - v[i + 1];
                } else {
                    ans += v[i + 1] - v[i];
                }
            }
            cout << ans << '\n';
        } else {
            ll ans = v[m - 1] + abs(v[0]);
            for (int i = 1; i < m - 1; i += 2) {
                if (v[i] >= v[i + 1]) {
                    ans += v[i] - v[i + 1];
                } else {
                    ans += v[i + 1] - v[i];
                }
            }
            cout << ans << '\n';
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    cout.precision(15);

    int T = 1;
    cin >> T;
    while (T--) {
        sol();
    }
}

//2 7
//10 3 7 1 4 6 3