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

const int N = 1e5 + 5;
set<int> g[N];
void add(int f, int t) {
    g[f].insert(t);
    g[t].insert(f);
}

void clr(int n) {
    n += 2;
    for (int i = 0; i <= n; ++i) {
        g[i].clear();
    }
}

int res = 0;
int st[N];
int n, m;

// set<int> stt;
void dfs(int u, int go) {
    st[u] = 1;

    int acc = 0;
    for (auto &it : g[u]) {
        if (!st[it]) {
            if (it == go) {
                dfs(go, go + 1);
            } else
                acc = 1;
        }
    }
    if (!st[go])
        if (acc) {
            add(u, go);
            ++res;
            dfs(go, go + 1);
        }
    if (u == 1) {
        for (int i = 1; i <= n; ++i) {
            if (!st[i]) {
                if (g[1].find(i) == g[1].end()) {
                    add(1, i);
                    ++res;
                }
                dfs(i, i + 1);
            }
        }
    }
}

int a, b;
void solve() {
    cin >> n >> m;
    clr(n);

    res = 0;
    for (int i = 1; i <= n; ++i)
        st[i] = 0;
    for (int i = 1; i <= m; ++i) {
        cin >> a >> b;
        add(a, b);
    }
    dfs(1, 2);
    cout << res << '\n';
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    while (n--)
        solve();
    return 0;
}