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

int T;
int n,m;

bool bri[100100];
vector<int> adj[100100];
vector<int> ind[100100];

vector<int> adj2[100100];

int aa,bb;
int r,c;
int ra[100100],lw[100100];
int co[100100];
bool vis[100100];
int cnt,sol;
int dp[100100];
void bridge(int nd,int p){
    ra[nd]=r;
    lw[nd]=r;
    r++;
    for(int i=0;i<adj[nd].size();i++){
        int ch=adj[nd][i];
        int id=ind[nd][i];
        if(ch==p)continue;
        if(ra[ch]==0){
            bridge(ch,nd);
            if(lw[ch]==ra[ch]){
                bri[id]=true;
            }
            lw[nd]=min(lw[nd],lw[ch]);
        } else {
            lw[nd]=min(lw[nd],ra[ch]);
        }
    }
}

void comp(int nd){
    vis[nd]=true;
    co[nd]=c;
    for(int i=0;i<adj[nd].size();i++){
        int ch=adj[nd][i];
        int id=ind[nd][i];
        if(bri[id])continue;
        if(vis[ch])continue;
        comp(ch);
    }
}

void diameter(int nd,int p){
    dp[nd]=0;

    int mx=-1,mx2=-1;
    for(int i=0;i<adj2[nd].size();i++){
        int ch=adj2[nd][i];
        if(ch==p)continue;
        diameter(ch,nd);
        dp[nd]=max(dp[nd],dp[ch]+1);
        if(dp[ch]>mx2){
            mx2=dp[ch];
        }
        if(mx2>mx){
            swap(mx2,mx);
        }
    }
    sol=max(sol,mx2+mx+2);
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&m);
        cnt=0;
        sol=0;
        r=1;
        c=1;
        for(int i=1;i<=n;i++){
            adj[i].clear();
            adj2[i].clear();
            ind[i].clear();
            ra[i]=0;
            lw[i]=0;
            co[i]=0;
            dp[i]=0;
            vis[i]=false;
        }
        for(int i=1;i<=m;i++){
            bri[i]=false;
        }
        for(int i=1;i<=m;i++){
            scanf("%d %d",&aa,&bb);
            adj[aa].push_back(bb);
            adj[bb].push_back(aa);

            ind[aa].push_back(i);
            ind[bb].push_back(i);
        }
        bridge(1,1);
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                comp(i);
                c++;
            }
        }
        c--;
        for(int i=1;i<=n;i++){
            for(int j=0;j<adj[i].size();j++){
                int ch=adj[i][j];
                int id=ind[i][j];
                if(bri[id]){
                    cnt++;
                    adj2[ co[i] ].push_back( co[ch] );
                }
            }
        }
        cnt/=2;
        diameter(1,1);
        printf("%d\n",cnt-sol);
    }
}