//#pragma GCC optimize("O3,unroll-loops")
#include <vector>
//#pragma GCC target("avx2")
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define segl i*2+1, l, (r + l) / 2
#define segr i*2+2, (r + l) / 2, r

const long long MOD = 1e9 + 7;
const int maxn = 2e5 + 5;

template<typename T, typename K>
istream& operator>>(istream& a, pair<T, K>& b) {
    a >> b.first >> b.second;
    return a;
}

template<typename T>
istream& operator>>(istream& a, vector<T>& b) {
    for(auto&i : b)
        a >> i;
    return a;
}

template<typename T, typename K>
ostream& operator<<(ostream& a, pair<T, K>& b) {
    a << b.first << ' ' << b.second;
    return a;
}

template<typename T>
ostream& operator<<(ostream& a, vector<T>& b) {
    for(auto& i : b)
        a << i << ' ';
    return a;
}

/*
                               .
                              .#.
                             .z@z.
                            .z#@#z.
                           .z#@@@#z.
                          .z#@@@@@#z.
                            `^#@#^`
                              .@.
                              .@.
                            ._z@z_.
                        ._z@#^` `^#@z_.
                       @#^`         `^#@
                       @               @
                       @z_.         ._z@
                        `^#@z_.  ._z@#^`
                    ._z@#^` `^#@#^`  `^#@z_.
                ._z@#^`                    `^#@z_.
      ._z#z_. .@#^`                            `^#@.  ._z#z_.
    ._z###@@@#^`                                  `^#@@@@@###z_.
  ._z###@@@@@#^`                                  `^#@@@@@@###z_.
 ._z###@@@@@#^`                                    `^#@@@@@@@###z_.
.zz###@@###^^`                                      ``^^###@@@@@##zz..
 */

/*struct Node {
    int sum = 0;
    vector<int> sol;
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    vector<int> sum(m + 1, 0);
    cin >> x;
    for(int i = 0; i<m; ++i) {
        sum[i + 1] -= sum[i];
        sum[i + 1] += x[i];
    }
    vector<vector<Node>> dp(m + 1, vector<Node>(n, {-4000000000000000, {}}));
    for(int j = 0; j<n; ++j) {
        dp[0][j].sum = 0;
        dp[0][j].sol = vector<int>(0);
    }
    for(int i = 1; i<=m; ++i) {
        for(int j = 0; j<n; ++j) {
            for(int sl = i - 1; sl >= 0; --sl) {
                for(int b = 0; b<n; ++b) {
                    int nw = ((i - sl) % 2 == 0 ? 1 : -1) * dp[sl][b].sol[j] + sum[i] - sum[sl];
                    if(dp[sl][b].sum - dp[sl][b].sol[j] + nw > dp[i][j].sum) {
                        dp[i][j].sum = dp[sl][b].sum - dp[sl][b].sol[j] + nw;
                        dp[i][j].sol = dp[sl][b].sol;
                        dp[i][j].sol[j] = nw;
                    }
                }
            }
            cout << i << ' ' << j << endl;
        }
    }
    int mx = -4e15;
    for(int i = 0; i<n; ++i) {
        mx = max(dp[m][i].sum, mx);
    }
    cout << mx << endl;
}*/

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    cin >> x;
    bool msk = m <= 18 && n == 2, r = 1;
    for(int i = 1; i<m; ++i) {
        if(x[i] != x[i - 1])
            r = 0;
    }
    if(r) {
        int sum = x[0]*min(n, m);
        int overflow = m - min(n, m);
        if(overflow % 2) {
            cout << sum - x[0] << '\n';
        } else {
            cout << sum << '\n';
        }
    } else if(msk) {
        int mm = 1ll << m;
        int mx = -4e15;
        for(int i = 0; i<mm; ++i) {
            pair<int, int> sms = {0, 0};
            for(int j = 0; j<m; ++j) {
                if((i >> j) & 1) {
                    sms.first = x[j] - sms.first;
                } else {
                    sms.second = x[j] - sms.second;
                }
            }
            if(sms.first + sms.second > mx)
                mx = sms.first + sms.second;
        }
        cout << mx << '\n';
    } else {
        exit(228);
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}
