#include<iostream>

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cmath>

#include<ctime>

#include<set>

#include<map>

#include<stack>

#include<cstring>

#define inf 2147483647

#define ls rt<<1

#define rs rt<<1|1

#define lson ls,nl,mid,l,r

#define rson rs,mid+1,nr,l,r

#define N 200010

#define For(i,a,b) for(int i=a;i<=b;i++)

#define p(a) putchar(a)

#define g() getchar()

using namespace std;

int T;

int n,m,x,y,cnt,col,now,S,Max;

int dfn[N],low[N],c[N],ans;

bool vis[N];

struct node{

    int n;

    node *next;

}*e[N];

stack<int>s;

struct edge{

    int x;int y;

}a[N];

void in(int &x){

    int y=;

    char c=g();x=;

    while(c<''||c>''){

        if(c=='-')y=-;

        c=g();

    }

    while(c<=''&&c>=''){

        x=(x<<)+(x<<)+c-'';c=g();

    }

    x*=y;

}

void o(int x){

    if(x<){

        p('-');

        x=-x;

    }

    if(x>)o(x/);

    p(x%+'');

}

void push(int x,int y){

    node *p;

    p=new node();

    p->n=y;

    if(e[x]==)

        e[x]=p;

    else{

        p->next=e[x]->next;

        e[x]->next=p;

    }

}

void tarjan(int x,int fa){

    dfn[x]=low[x]=++cnt;

    vis[x]=;

    s.push(x);

    for(node *i=e[x];i;i=i->next){

        if(!dfn[i->n]){

            tarjan(i->n,x);

            low[x]=min(low[x],low[i->n]);

        }

        else

            if(vis[i->n]&&i->n!=fa)

                low[x]=min(low[x],dfn[i->n]);

    }

    if(low[x]==dfn[x]){

        col++;

        do{

            ans++;

            now=s.top();

            c[now]=col;

            s.pop();

            vis[now]=0;

        }while(x!=now);

    }

}

void dfs(int x,int fa,int deep){

    if(Max<deep){

        Max=deep;

        S=x;

    }

    for(node *i=e[x];i;i=i->next)

        if(i->n!=fa)

            dfs(i->n,x,deep+);

}

void clear(){

    memset(vis,,sizeof(vis));

    memset(dfn,,sizeof(dfn));

    memset(c,,sizeof(c));

    memset(low,,sizeof(low));

    memset(e,,sizeof(e));

    Max=;

    col=;

    cnt=;

}

int main(){

    in(T);

    while(T--){

        clear();

        in(n);in(m);

        For(i,,m){

            in(x);in(y);

            a[i].x=x;

            a[i].y=y;

            push(x,y);

            push(y,x);

        }

        tarjan(,);

        memset(e,,sizeof(e));

        For(i,,m)

            if(c[a[i].x]!=c[a[i].y]){

                push(c[a[i].x],c[a[i].y]);

                push(c[a[i].y],c[a[i].x]);

            }

        dfs(,,);

        Max=;

        dfs(S,S,);

        o(col-Max-);p('\n');

    }

    return ;

}