#include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #define maxn 111111

 using namespace std;

 int f[maxn],du[maxn],odd[maxn],book[maxn];

 int getf(int v){

     if(f[v] == v){

         return v;

     }else{

         f[v] = getf(f[v]);

         return f[v];

     }

 }

 void merge(int u,int v){

     int a = getf(u);

     int b = getf(v);

     if(a!=b)

         f[b] = a;

 }

 int main(){

     int t;

     scanf("%d",&t);

     while(t--){

         memset(du,,sizeof(du));//统计每个节点的度数

         memset(odd,,sizeof(odd));//统计每个联通分量度数为奇数的节点个数

         memset(book,,sizeof(book));//标记该点是否需要去

         int n,m;

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

         for(int i = ;i<=n;i++)//初始化

             f[i] = i;

         int u,v;

         while(m--){

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

             du[u]++;

             du[v]++;

             book[u] = ;

             book[v] = ;

             merge(u,v);

         }

         int cnt = ;//需要边的数量

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

             if(book[i]){

                 if(f[i] == i)

                     cnt++;

                 if(du[i]&)//度数为奇数时，对其并查集根节点的值进行更新

                     odd[getf(i)]++;

             }

         }

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

             if(f[i] == i)

                 cnt += max(,(odd[i]-)/);//统计每个联通分量的度数为奇数的节点所需要的边的个数

         }

         printf("%d\n",cnt-);

     }

     return ;

 }