///by Saton.
#include<bits/stdc++.h>
#define PI acos(-1)
#define fi first
#define se second 
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define LL long long
#define ll __int128
#define DD double double
#define LD long double
#define rep(i,a,b) for(LL i = (a);i <= (b);i ++)
#define lep(i,a,b) for(LL i = (a);i >= (b);i --)
#define FLUSH fflush(stdout)
using namespace std;
const int N = 1e5 + 10,mod =  1e9+7,P = 131;
LL n,m,k;
struct DSU {
    std::vector<int> f;
    std::vector<int> size;
 
    DSU(int n) : f(n), size(n) {
        std::iota(f.begin(), f.end(), 0);
        std::fill(size.begin(), size.end(), 1);
    }
 
    int find(int x) {
        while (x != f[x])
            x = f[x] = f[f[x]];
        return x;
    }
 
    void Union(int x, int y) {
        if (find(x) == find(y))
            return;
 
        size[find(x)] += size[find(y)];
        f[find(y)] = find(x);
    }
 
    int blockSize(int x) {
        return size[find(x)];
    }
};

int sg(int x) {
    if (x == 0)
        return 0;
    return 2 - x % 2;
}

void solve() {
    cin >> n >> m;
    vector<vector<int>> e(n+1);
    DSU dsu(n+1);
    rep(i,1,m) {
        int u,v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    int SG = 0;
    rep(i,1,n) {
        if(i == dsu.find(i)) {
            SG ^= sg(dsu.blockSize(i));
        }
    }    
    
    int ans = 0;
    vector<int> size(n+1,0);
    function<void(int,int)> dfs = [&](int x,int fa) {
        int tempSG = 0;
        size[x] = 1;
        for(int y : e[x]) {
            if(y == fa) continue;
            dfs(y,x);
            tempSG ^= sg(size[y]);
            size[x] += size[y];
        }
        
        tempSG ^= sg(dsu.blockSize(x) - size[x]);
        //删点
        if(SG^tempSG == 0) ans ++;
        //删边
        if(fa!=0 && SG^sg(size[x])^sg(dsu.blockSize(x) - size[x])==0) ans ++;
    };
    
    rep(i,1,n) {
        if(i == dsu.find(i)) {
            SG ^= sg(dsu.blockSize(i));
            dfs(i,0);
            SG ^= sg(dsu.blockSize(i));
        }
    }
    
    cout << ans << '\n';
} 

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while(T --) { 
        solve();
    }
    // solve();
       
    return 0;
}  
/*   /\_/\
*   (= ._.)
*   / >  \>
*/