#include<bits/stdc++.h>

using namespace std;

#define ll long long int
#define iter(i,a) for( typeof(a.begin()) i=a.begin();i!=a.end();i++)
#define REP(p,a,b) for(int p=a;p<b;p++)
#define pb(f) push_back(f)
#define mkp(a,b) make_pair(a,b)
#define fst first
#define snd second
#define pii pair<int,int>
#define ins(a) insert(a)
#define maxV 100005

ll visited[maxV];
int parent[maxV];
vector<int> adj[maxV];
vector<int> adj1[maxV];
ll disc[maxV];
ll low[maxV];
set<pii> ans;
ll cnt;

struct subset
{
    int parent;
    int rank;
}subsets[maxV];

void initialize()
{
    memset(visited,0,sizeof(visited));
    memset(parent,-1,sizeof(parent));
}

void initializer(int V)
{
    REP(i,1,V+1)
    {
        subsets[i].parent=i;
        subsets[i].rank=0;
    }
}

void bridge(int u)
{
    static ll time = 0;
    visited[u] = 1;
    disc[u] = low[u] = ++time;
    iter(i,adj[u])
    {
        int v = *i;
        if (!visited[v])
        {
            parent[v] = u;
            bridge(v);
            low[u]=min(low[u],low[v]);
            if (low[v] > disc[u])
              cnt++,ans.insert(mkp(u,v)),ans.insert(mkp(v,u));
        }
        else if (v != parent[u])
            low[u]=min(low[u],disc[v]);
    }
}

void dfs(int s,ll dis)
{
    visited[s]=dis;
    iter(i,adj1[s])
        if(visited[*i]==-1)
            dfs(*i,dis+1);
}

int find(int x)
{
    if(subsets[x].parent!=x)
        subsets[x].parent=find(subsets[x].parent);
    return subsets[x].parent;
}

void Union(int x,int y)
{
    int xroot=find(x);
    int yroot=find(y);

    if(subsets[xroot].rank>subsets[yroot].rank)
        subsets[yroot].parent=xroot;
    else if(subsets[xroot].rank<subsets[yroot].rank)
        subsets[xroot].parent=yroot;
    else
        subsets[xroot].parent=yroot,subsets[yroot].rank++;
}

void DSU(int n)
{
    REP(i,1,n+1)
    {
        REP(j,0,adj[i].size())
        {
            if(ans.find(pii(i,adj[i][j]))==ans.end())
            {
                int xroot=find(i);
                int yroot=find(adj[i][j]);
                if(xroot!=yroot)
                    Union(xroot,yroot);
            }
        }
    }
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    int t,a,b,n,m;
    cin>>t;
    while(t--)
    {
        ll maxi=-1;
        cnt=0;
        cin>>n>>m;
        REP(i,0,maxV)
            adj[i].clear(),adj1[i].clear();
        ans.clear();
        REP(i,0,m)
        {
            cin>>a>>b;
            adj[a].pb(b);
            adj[b].pb(a);
        }
        initialize();
        REP(i,1,n+1)
        if(!visited[i])
            bridge(i);
        initializer(n);
        DSU(n);
        iter(i,ans)
        {
            pii p;
            p.fst=i->fst;
            p.snd=i->snd;
            if(find(p.fst)!=find(p.snd))adj1[find(p.fst)].pb(find(p.snd));
        }
        memset(visited,-1,sizeof(visited));
        REP(i,1,n+1)
            if(visited[i]==-1)
                dfs(i,0LL);
        REP(i,1,n+1)
            maxi=max(maxi,visited[i]);
        cout<<cnt-maxi<<endl;
    }
	return 0;
}