#include <bits/stdc++.h>
#define MOD ((ll) (1e9 + 7))
#define all(x) (x).begin(), (x).end()
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;
using namespace std;
ll combs(ll n, ll k) {
    ll i, result;
    result = 1;
    for(i = n - k + 1; i <= n; i++)
        result *= i;
    for(i = 2; i <= k; i++)
        result /= i;
    return result;
}
int main() {
    FastIO;
    ll i, j, k, oc, fr, unc, ans, T;
    cin >> T;
    vector<ll> N(T);
    vector<ll> K(T);
    vector<vector<array<ll, 2>>> ranges(T);
    for(i = 0; i < T; i++) {
        cin >> N[i] >> K[i];
        ranges[i].resize(K[i]);
        for(j = 0; j < K[i]; j++) {
            cin >> ranges[i][j][0] >> ranges[i][j][1];
            ranges[i][j][1]++;
        }
    }
    for(i = 0; i < T; i++) {
        set<ll> eps;
        for(j = 0; j < K[i]; j++)
            eps.insert(all(ranges[i][j]));
        vector<ll> epv(all(eps));
        eps.clear();
        vector<array<ll, 2>> indices(K[i]);
        for(j = 0; j < K[i]; j++) {
            for(k = 0; k < 2; k++)
                indices[j][k] = lower_bound(all(epv), ranges[i][j][k]) - epv.begin();
        }
        sort(all(indices), [](auto &a, auto &b) { return (a[1] - a[0]) < (b[1] - b[0]); });
        // 0 = uncat, 1 = odd, 2 = even
        vector<ll> labels(epv.size() - 1, 0);
        for(j = 0; j < K[i]; j++) {
            oc = 0;
            unc = -1;
            for(k = indices[j][0]; k < indices[j][1]; k++) {
                switch(labels[k]) {
                    case 0:
                        assert(unc == -1);
                        unc = k;
                        break;
                    case 1:
                        oc++;
                }
            }
            if(oc % 2) {
                if(unc != -1)
                    labels[unc] = 2;
            }
            else {
                if(unc == -1) {
                    cout << "0\n";
                    goto next;
                }
                labels[unc] = 1;
            }
        }
        ans = 0;
        for(j = 0; j < labels.size(); j++) {
            fr = epv[j + 1] - epv[j];
            for(k = (labels[j] == 1); k <= fr; k += 2)
                ans += combs(fr, k);
        }
        cout << ans << '\n';
        next:;
    }
    return 0;
}