#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;

struct edge{
    int f;
    int t;
    bool is;
    edge(){
        is=false;
    }
};
edge list[100100];
vector<edge*> adj[100100];
vector<int> adj2[100100];
int comp[100100];
int cc=1;
int n,m;
int t;
int rnk[100100],rr=0;
int low[100100];
bool vis[100100];
int sol=0;
int dp[100100];
void dfs3(int nd,int p){
    int mx=-1,smx=-1;
    dp[nd]=0;
    for(int i=0;i<adj2[nd].size();i++){
        int ch=adj2[nd][i];
        if(ch==p)continue;
        dfs3(ch,nd);
        dp[nd]=max(dp[nd],dp[ch]+1);
        if(smx<dp[ch])smx=dp[ch];
        if(smx>mx)swap(smx,mx);
    }
    sol=max(sol,mx+smx+2);
}
void dfs2(int nd){
    comp[nd]=cc;
    vis[nd]=true;
    for(int i=0;i<adj[nd].size();i++){
        int ch;
        if(adj[nd][i]->t==nd)ch=adj[nd][i]->f;
        else ch=adj[nd][i]->t;
        if(!vis[ch] && !adj[nd][i]->is)
        dfs2(ch);
    }
}

void dfs(int nd,int p){
    rnk[nd]=rr++;
    low[nd]=rnk[nd];
    vis[nd]=true;
    for(int i=0;i<adj[nd].size();i++){
        int ch;
        if(adj[nd][i]->t==nd)ch=adj[nd][i]->f;
        else ch=adj[nd][i]->t;
        if(vis[ch]){
            if(ch!=p)
            low[nd]=min(low[nd],rnk[ch]);
        } else {
            dfs(ch,nd);
            low[nd]=min(low[nd],low[ch]);
            if(low[ch]==rnk[ch]){
                adj[nd][i]->is=true;
            }
        }


    }
}

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        rr=0;
        cc=1;
        sol=0;

        for(int i=0;i<m;i++){
            scanf("%d %d",&list[i].f,&list[i].t);
            adj[list[i].t].push_back(&list[i]);
            adj[list[i].f].push_back(&list[i]);
        }
        dfs(1,1);
        for(int i=1;i<=n;i++){
            vis[i]=false;
        }
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                dfs2(i);
                cc++;
            }

        }
        cc--;
        for(int i=1;i<=n;i++){
            adj[i].clear();
        }
        int ttt=0;
        for(int i=0;i<m;i++){
            if(list[i].is){
                ttt++;
                adj2[comp[list[i].f]].push_back(comp[list[i].t]);
                adj2[comp[list[i].t]].push_back(comp[list[i].f]);
            }
        }

        dfs3(1,1);
        for(int i=1;i<=cc;i++){
            adj2[i].clear();
        }
        printf("%d\n",ttt-sol);
    }
}