#include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<stack>

 using namespace std;

 const int maxn=+;

 struct Edge

 {

     int to,next;

     bool flag;//标记是否是桥

 }edge[maxn*];

 stack<int> S;

 int n,m;

 int head[maxn],tot;

 int low[maxn],dfn[maxn],belong[maxn];

 int index,top;

 int block;//边双连通块数

 bool instack[maxn];

 int bridge;//桥的数目

 int e[maxn][];

 int deep;   //最长直径

 int pos;    //最长直径端点

 void addedge(int u,int v)

 {

     edge[tot].to=v,edge[tot].next=head[u],edge[tot].flag=;

     head[u]=tot++;

 }

 void Tarjan(int u,int pre)

 {

     int v;

     low[u]=dfn[u]=++index;

     S.push(u);

     instack[u]=;

     for(int i=head[u];~i;i=edge[i].next)

     {

         v=edge[i].to;

         if(v==pre)continue;

         if(!dfn[v])

         {

             Tarjan(v,u);

             if(low[u]>low[v])low[u]=low[v];

             if(low[v]>dfn[u])

             {

                 bridge++;

                 edge[i].flag=;

                 edge[i^].flag=;

             }

         }

         else if(instack[v]&&low[u]>dfn[v])

             low[u]=dfn[v];

     }

     if(low[u]==dfn[u])

     {

         block++;

         do

         {

             v=S.top(); S.pop();

             instack[v]=;

             belong[v]=block;

         }

         while(v!=u);

      }

 }

 void init()

 {

     memset(dfn,,sizeof(dfn));

     index=block=top=bridge=tot=;

     memset(head,-,sizeof(head));

 }

 //邻接表寻找树的直径

 void dfs(int u,int fa,int cnt)

 {

     if(cnt>deep)  {deep=cnt;pos=u;}

     for(int i=head[u];~i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v!=fa)  dfs(v,u,cnt+);

     }

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         init();

         for(int i=;i<=m;i++)

         {

             scanf("%d%d",&e[i][],&e[i][]);

             addedge(e[i][],e[i][]);

             addedge(e[i][],e[i][]);

         }

         Tarjan(,);

         //缩点，重建图

         tot=;

         memset(head,-,sizeof(head));

         int ans=;

         for(int i=;i<=m;i++)

         {

             int u=belong[e[i][]], v=belong[e[i][]];

             if(u!=v)

             {

                 ans++;

                 addedge(u,v);

                 addedge(v,u);

             }

         }

         deep=;

         dfs(,,);

         deep=;

         dfs(pos,pos,);

         printf("%d\n",ans-deep);

     }

     return ;

 }