#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;
}
ll solve(const vector<bool> &is_odd, const vector<ll> &epv, const vector<vector<ll>> &swith) {
    bool can[2] { true, true };
    ll i, j, bc, ans;
    ans = 0;
    if(is_odd.size() == epv.size()) {
        for(i = 1; i < epv.size(); i++) {
            bc = epv[i] - epv[i - 1];
            for(j = is_odd[i]; j <= bc; j += 2)
                ans += combs(bc, j);
        }
    }
    else {
        for(const auto &x : swith[is_odd.size()]) {
            if(is_odd[x])
                can[1] = false;
            else
                can[0] = false;
            if(!can[0] && !can[1])
                return 0;
        }
        for(i = 0; i < 2; i++) {
            if(!can[i])
                continue;
            vector<bool> nio = is_odd;
            nio.push_back(i ^ nio.back());
            ans += solve(nio, epv, swith);
        }
    }
    if(ans)
        cout << ans << '\n';
    return ans;
}
int main() {
    FastIO;
    ll i, j, 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][0]--;
        }
    }
    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<vector<ll>> swith(epv.size());
        for(j = 0; j < K[i]; j++)
            swith[lower_bound(all(epv), ranges[i][j][1]) - epv.begin()].push_back(lower_bound(all(epv), ranges[i][j][0]) - epv.begin());
        cout << solve({ false }, epv, swith) << '\n';
    }
    return 0;
}