//SPOJ - UOFTCG 树的最小路径覆盖

 #include <bits/stdc++.h>

 #include <vector>

 using namespace std;

 #define ll long long

 const int mod = 1e9+;

 const int maxn=;

 const int N = 1e5+;

 int cnt;

 int head[N];

 struct edge{

     int to,next;

 }e[N<<];

 void addedge(int u,int v){

     e[cnt].to=v,e[cnt].next=head[u],head[u]=cnt++;

     e[cnt].to=u,e[cnt].next=head[v],head[v]=cnt++;

 }

 int cov[N];

 bool vis[N],used[N];

 void dfs(int u,int f){

     used[u]=;

     cov[u]=;

     int tot=;

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

         int v=e[i].to;

         if(v==f) continue;

         dfs(v,u);

         cov[u]+=cov[v];

         if(!vis[v]) tot++;

     }

     if(tot>=) cov[u]-=,vis[u]=;

     else if(tot==) cov[u]-=;

 }

 int main(){

     // freopen("in.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--){

         cnt=;

         memset(used,false,sizeof(used));

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

         memset(cov,,sizeof(cov));

         memset(vis,false,sizeof(vis));

         int n,m;

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

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

             int u,v;

             scanf("%d%d",&u,&v);

             addedge(u,v);

         }

         int ans=;

         for(int i=;i<=n;i++){

            if(!used[i]) dfs(i,),ans+=cov[i];

         }

         // cout<<cov[1]<<endl;

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

     }

 }