#include <bits/stdc++.h>
using namespace std;
#define int long long

// Binary search to find the type of soldier at position pos
int find_type(int pos) {
    int lo = 1, hi = 2e6;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        int sum = mid * (mid + 1) / 2;
        if (sum < pos)
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo;
}

// Get starting index of type k
int start_index(int k) {
    return (k - 1) * k / 2 + 1;
}

int get_type(int pos, map<int, int> &modified) {
    if (modified.count(pos)) return modified[pos];
    return find_type(pos);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N, M;
        cin >> N >> M;

        set<int> positions_to_check;
        vector<pair<int, int>> swaps(M);
        for (int i = 0; i < M; ++i) {
            int x, y;
            cin >> x >> y;
            swaps[i] = {x, y};
            for (int d = -1; d <= 1; ++d) {
                if (x + d >= 1) positions_to_check.insert(x + d);
                if (y + d >= 1) positions_to_check.insert(y + d);
            }
        }

        map<int, int> pos_type;
        for (int pos : positions_to_check) {
            pos_type[pos] = find_type(pos);
        }

        for (auto [x, y] : swaps) {
            swap(pos_type[x], pos_type[y]);
        }

        int power = 0;
        for (int pos : positions_to_check) {
            if (pos_type.count(pos) && pos_type.count(pos + 1)) {
                if (pos_type[pos] == pos_type[pos + 1]) power++;
            }
        }

        cout << power << '\n';
    }

    return 0;
}