#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pi pair<int,int>
#define adjs(name, type, size) vector<vector<type>>name(size)
#define adjpass(name, type) vector<vector<type>>&name
#define killua ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
int cases = 1;
int timer = 1;
set<pi > bridges;

void dfsSCC(int node, int dad, vector<int> &dfn, vector<int> &lowlink, adjpass(v, int)) {
    dfn[node] = lowlink[node] = timer++;
    for (auto i: v[node]) {
        if (i == dad)
            continue;
        if (dfn[i] == -1) { //not vis
            dfsSCC(i, node, dfn, lowlink, v);
            lowlink[node] = min(lowlink[node], lowlink[i]);
            if (lowlink[i] > dfn[node]) {
                bridges.insert({min(node, i), max(node, i)});
            }
        } else {
            lowlink[node] = min(lowlink[node], dfn[i]);
        }
    }
}

void dfs(int node, vector<set<int >> &v, vector<int> &vis, int &last, int &mx, int cur) {
    vis[node] = 1;
    if (cur > mx) {
        mx = cur;
        last = node;
    } else if (cur == mx) {
        last = min(last, node);
    }
    for (auto i: v[node]) {
        if (!vis[i]) {
            dfs(i, v, vis, last, mx, cur + 1);
        }
    }
}

class DSU {
private:
    vector<int> rank, par, size;
public:
    DSU(int n = 0) {
        rank.resize(n + 1);
        par.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++)
            par[i] = i;
    }

    int findUpar(int node) {
        if (node == par[node])
            return node;
        return par[node] = findUpar(par[node]);//path comp
    }

    void unionbyRank(int u, int v) {
        int UparU = findUpar(u);
        int UparV = findUpar(v);
        if (UparU == UparV)
            return;
        if (rank[UparU] < rank[UparV]) {
            par[UparU] = UparV;
        } else {
            par[UparV] = UparU;
            rank[UparU] += (rank[UparU] == rank[UparV]);
        }
    }

    void unionbySize(int u, int v) {
        int UparU = findUpar(u);
        int UparV = findUpar(v);
        if (UparU == UparV)
            return;
        if (size[UparU] < size[UparV]) {
            par[UparU] = UparV;
            size[UparV] += size[UparU];
        } else {
            par[UparV] = UparU;
            size[UparU] += size[UparV];
        }
    }
};

void gon() {
    int n, m;
    cin >> n >> m;
    adjs(v, int, n + 5);
    vector<pi > ed;
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        ed.push_back({min(l, r), max(l, r)});
        v[l].push_back(r);
        v[r].push_back(l);
    }

    vector<int> dfn(n + 5, -1), lowlink(n + 5, -1);
    timer = 1;
    bridges.clear();
    for (int i = 1; i <= n; i++) {
        if (dfn[i] == -1) {
            dfsSCC(i, -1, dfn, lowlink, v);
        }
    }
    map<pi, int> mp;
    for (auto i: bridges)
        mp[i] = 1;
    DSU d(n + 5);
    for (auto i: ed) {
        if (!mp.count(i)) {
            d.unionbySize(i.first, i.second);
        }
    }
    vector<int> comp(n + 5, 1e9);
    for (int i = 1; i <= n; i++) {
        comp[d.findUpar(i)] = min(comp[d.findUpar(i)], i);
    }
    vector<set<int >> mst(n + 5);
    int cot = 0;
    for (auto i: ed) {
        if (!mp.count(i)) {
            continue;
        }
        cot++;
        int a = comp[d.findUpar(i.first)];
        int b = comp[d.findUpar(i.second)];
        mst[a].insert(b);
        mst[b].insert(a);
    }
    int St = 1;
    int last = 1;
    int mx = 0;
    int cur = 0;
    vector<int> vis(n + 5);
    dfs(St, mst, vis, last, mx, cur);
    vis.assign(n + 5, 0);
    int L = last;
    St = last;
    mx = 0;
    cur = 0;
    dfs(St, mst, vis, last, mx, cur);
    cout << cot - mx << endl;
}

int32_t main() {
    killua;
    int t = 1;
    if (cases) cin >> t;
    while (t--) {
        gon();
    }
}