// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1034567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-9
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
using namespace std;
// mylittledoge

/* Edmonds' blossom algorithm
match[v]: vertex matched to it / -1
finds a tree of alternating paths rooted at R; the parent of v is prev[v] or match[v]
also builds a tree of blossoms
'k, I say blossoms, but each blossom = its base
*/

// based on https://sites.google.com/site/indy256/algo/edmonds_matching

int lca(vector<int> &cur_blossom, vector<int> &match, vector<int> &prev, int u, int v) {
	// in the tree of blossoms
	// lists blossoms on paths to the root, finds the first common one
	set<int> blossoms_visited;

	int b =cur_blossom[u];
	while(true) {
		blossoms_visited.insert(b);
		if(match[b] == -1 || prev[match[b]] == -1) break;
		b =cur_blossom[prev[match[b]]];}

	b =cur_blossom[v];
	while(true) {
		if(blossoms_visited.find(b) != end(blossoms_visited)) return b;
		b =cur_blossom[prev[match[b]]];}

	return b;}

int find_aug_path(vector< vector<int> > &G, vector<int> &match, vector<int> &prev, int R) {
	int N =G.size();
	vector<bool> vis(N,false);

	vector<int> cur_blossom(N);
	for(int i =0; i < N; i++) cur_blossom[i] =i;

	queue<int> q;
	q.push(R);
	vis[R] =true;

	while(!q.empty()) {

		ALL_THE(G[q.front()],it) if(*it != match[q.front()]) {

			// in the same blossom, already processed
			if(cur_blossom[*it] == cur_blossom[q.front()]) continue;

			if(prev[*it] == -1 && !(match[*it] != -1 && prev[match[*it]] != -1)) {
				if(*it == R) continue;
				prev[*it] =q.front();
				if(match[*it] == -1) return (*it); // augmenting path to *it
				vis[match[*it]] =true;
				q.push(match[*it]);
				continue;}

			if(*it != R && !(match[*it] != -1 && prev[match[*it]] != -1)) continue;

			// blossom found
			
			int new_blossom =lca(cur_blossom,match,prev,q.front(),*it);
			vector<bool> in_new_blossom(N,false);

			int v =q.front(), parent_v =*it;
			while(cur_blossom[v] != new_blossom) {
				in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true;
				prev[v] =parent_v;
				parent_v =match[v];
				v =prev[match[v]];}

			v =*it, parent_v =q.front();
			while(cur_blossom[v] != new_blossom) {
				in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true;
				prev[v] =parent_v;
				parent_v =match[v];
				v =prev[match[v]];}

			for(int i =0; i < N; i++) if(in_new_blossom[cur_blossom[i]]) {
				cur_blossom[i] =new_blossom;
				if(vis[i]) continue;
				vis[i] =true;
				q.push(i);}
			
			}

		q.pop();}

	return -1;}

vector<bool> find_winning(vector< vector<int> > &G, vector<int> &match, vector<int> &prev, int R) {
	// find all vertices ending at even length alternating paths
	int N =G.size();
	vector<bool> is_winning(N,false);
	is_winning[R] =true;
	vector<bool> vis(N,false);

	vector<int> cur_blossom(N);
	for(int i =0; i < N; i++) cur_blossom[i] =i;

	queue<int> q;
	q.push(R);
	vis[R] =true;

	while(!q.empty()) {

		ALL_THE(G[q.front()],it) if(*it != match[q.front()]) {

			// in the same blossom, already processed
			if(cur_blossom[*it] == cur_blossom[q.front()]) continue;

			if(prev[*it] == -1 && !(match[*it] != -1 && prev[match[*it]] != -1)) {
				if(*it == R) continue;
				prev[*it] =q.front();
				vis[match[*it]] =true;
				is_winning[match[*it]] =true;
				q.push(match[*it]);
				continue;}

			if(*it != R && !(match[*it] != -1 && prev[match[*it]] != -1)) continue;

			// blossom found
			
			int new_blossom =lca(cur_blossom,match,prev,q.front(),*it);
			vector<bool> in_new_blossom(N,false);

			int v =q.front(), parent_v =*it;
			while(cur_blossom[v] != new_blossom) {
				in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true;
				prev[v] =parent_v;
				parent_v =match[v];
				v =prev[match[v]];}

			v =*it, parent_v =q.front();
			while(cur_blossom[v] != new_blossom) {
				in_new_blossom[cur_blossom[v]] =in_new_blossom[cur_blossom[match[v]]] =true;
				prev[v] =parent_v;
				parent_v =match[v];
				v =prev[match[v]];}

			for(int i =0; i < N; i++) if(in_new_blossom[cur_blossom[i]]) {
				cur_blossom[i] =new_blossom;
				is_winning[i] =true;
				if(vis[i]) continue;
				vis[i] =true;
				q.push(i);}
			
			}

		q.pop();}

	return is_winning;}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	for(int t =0; t < T; t++) {
		int N,M;
		cin >> N >> M;
		vector< vector<int> > G(N);
		for(int i =0; i < M; i++) {
			int a,b;
			cin >> a >> b;
			G[--a].push_back(--b);
			G[b].push_back(a);}

		// random maximal matching
		vector<int> match(N,-1);
		int ans =0, matching_sz =0;
		while(true) {
			// find all vertices that can matched
			vector<int> v;
			for(int i =0; i < N; i++) if(match[i] == -1) {
				bool m =false; // can it be matched?
				ALL_THE(G[i],it) if(match[*it] == -1) m =true;
				if(m) v.push_back(i);}
			if(v.empty()) break; // is maximal
			int x =v[rand()%v.size()];
			vector<int> w;
			ALL_THE(G[x],it) if(match[*it] == -1) w.push_back(*it);
			int y =w[rand()%w.size()];
			// match edge x-y
			matching_sz++;
			match[x] =y;
			match[y] =x;}

		// make it maximum
		for(int i =0; i < N; i++) if(match[i] == -1) {
			vector<int> prev(N,-1);
			int akt =find_aug_path(G,match,prev,i); // end of the found aug. path 
//			cout << i << " " << akt << "  ";
//			for(int j =0; j < N; j++) cout << prev[j] << " ";
//			cout << endl;
			if(akt == -1) continue;
			while(akt != -1) {
				int prev_akt =match[prev[akt]];
				match[akt] =prev[akt];
				match[prev[akt]] =akt;
				akt =prev_akt;}
			matching_sz++;}

//		cout << 2*matching_sz << " " << N << "\n";

		vector<bool> is_winning(N,false);
		for(int i =0; i < N; i++) if(match[i] == -1) {
			vector<int> prev(N,-1);
			vector<bool> v =find_winning(G,match,prev,i);
			for(int j =0; j < N; j++) if(v[j]) is_winning[j] =true;}

		for(int i =0; i < N; i++) if(is_winning[i]) ans++;
		cout << ans << "\n";
	}
	return 0;}

// look at my code
// my code is amazing