#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define USE_SLOW_ALGO 0
#define DEBUG 0
#define NMAX 2501

int v[NMAX][NMAX], nv[NMAX];
int N, M;

void ReadInput() {
	scanf("%d %d", &N, &M);
	int i, j, k;
	memset(nv, 0, sizeof(nv));
	for (k = 1; k <= M; k++) {
		scanf("%d %d", &i, &j);
		nv[i]++; nv[j]++;
		v[i][nv[i]] = j;
		v[j][nv[j]] = i;
	}
}

int used[NMAX], lcaused[NMAX], blossomused[NMAX], blossom[NMAX], baseused[NMAX];
int Mv[NMAX], p[NMAX], pused[NMAX], q[NMAX], base[NMAX], qli, qls, lcaidx;
int blossom_changed[NMAX], nblossom_changed, blossom_changed_idx[NMAX];
int pathidx, blossomidx;
 
int LCA(int a, int b, int excl = 0) {
	lcaidx++;
	for (;;) {
		if (baseused[a] != pathidx) {
			base[a] = a;
			baseused[a] = pathidx;
			//exit(1);
		}
		a = base[a];
		lcaused[a] = lcaidx;
		if (!Mv[a] || Mv[a] == excl)  break;
		if (pused[Mv[a]] != pathidx) {
			exit(11);
		}
		a = p[Mv[a]];
	}
	for (;;) {
		if (baseused[b] != pathidx) {
			base[b] = b;
			baseused[b] = pathidx;
			//exit(2);
		}
		b = base[b];
		if (lcaused[b] == lcaidx) return b;
		if (pused[Mv[b]] != pathidx) {
			exit(12);
		}
		b = p[Mv[b]];
	}
}

void MarkPath(int i, int b, int children) {
	while (1) {
		if (baseused[i] != pathidx) {
			base[i] = i;
			baseused[i] = pathidx;
		}
		if (base[i] == b) break;
		if (baseused[Mv[i]] != pathidx) {
			base[Mv[i]] = Mv[i];
			baseused[Mv[i]] = pathidx;
		}
		if (blossom_changed_idx[i] != blossomidx) {
			blossom_changed[nblossom_changed++] = i;
			blossom_changed_idx[i] = blossomidx;
		}
		if (blossom_changed_idx[base[i]] != blossomidx) {
			blossom_changed[nblossom_changed++] = base[i];
			blossom_changed_idx[base[i]] = blossomidx;
		}
		if (blossom_changed_idx[Mv[i]] != blossomidx) {
			blossom_changed[nblossom_changed++] = Mv[i];
			blossom_changed_idx[Mv[i]] = blossomidx;
		}
		if (blossom_changed_idx[base[Mv[i]]] != blossomidx) {
			blossom_changed[nblossom_changed++] = base[Mv[i]];
			blossom_changed_idx[base[Mv[i]]] = blossomidx;
		}
		blossom[base[i]] = blossom[base[Mv[i]]] = 1;
		blossomused[base[i]] = blossomused[base[Mv[i]]] = blossomidx;
		p[i] = children;
		pused[i] = pathidx;
		children = Mv[i];
		if (pused[Mv[i]] != pathidx) exit(333);
		i = p[Mv[i]];
	}
}

int FindAugmentingPath(int root, int excl = 0) {
	pathidx++;
	used[root] = pathidx;
	qli = qls = 0;
	q[qls++] = root;
	
	while (qli < qls) {
		int i = q[qli++];
		if (baseused[i] != pathidx) {
			base[i] = i;
			baseused[i] = pathidx;
		}
		for (int k = 1; k <= nv[i]; k++) {
			int j = v[i][k];
			if (baseused[j] != pathidx) {
				baseused[j] = pathidx;
				base[j] = j;
			}
			if (base[i] == base[j] || Mv[i] == j || j == excl) continue;
			if (j == root || (Mv[j] > 0 && pused[Mv[j]] == pathidx && Mv[j] != excl)) {
				int curbase = LCA(i, j, excl);
				blossomidx++;
				nblossom_changed = 0;
				MarkPath(i, curbase, j);
				MarkPath(j, curbase, i);
				for (int ll = 0; ll < nblossom_changed; ll++) {
					int l = blossom_changed[ll];
					if (baseused[l] != pathidx) {
						baseused[l] = pathidx;
						base[l] = l;
					}
					if (blossomused[base[l]] == blossomidx) {
						base[l] = curbase;
						baseused[l] = pathidx;
						if (used[l] != pathidx) {
							used[l] = pathidx;
							q[qls++] = l;
						}
					}
				}
			} else if (pused[j] != pathidx) {
				p[j] = i;
				pused[j] = pathidx;
				if (!Mv[j] || Mv[j] == excl) return j;
				j = Mv[j];
				used[j] = pathidx;
				q[qls++] = j;
			}
		}
	}
	return 0;
}
 
int MaxMatching(int excl = 0) {
	int i, j, k, l, c = 0;
	memset(Mv, 0, sizeof(Mv));
	for (i = 1; i <= N; i++) {
		if (Mv[i] || i == excl) continue;
		for (j = 1; j <= nv[i]; j++)
			if (!Mv[v[i][j]] && v[i][j] != excl) {
				Mv[i] = v[i][j];
				Mv[v[i][j]] = i;
				c++;
				if (DEBUG) fprintf(stderr, "[MaxMatching] initial edge %d-%d c=%d\n", i, v[i][j], c);
				break;
			}
	}
	for (i = 1; i <= N; i++)
		if (!Mv[i] && i != excl) {
			j = FindAugmentingPath(i, excl);
			if (!j) continue;
			c++;
			if (DEBUG) fprintf(stderr, "[MaxMatching] augmenting path %d-%d c=%d\n", i, j, c);
			while (j > 0) {
				k = p[j];
				l = Mv[k];
				if (DEBUG) fprintf(stderr, "  add edge %d-%d\n", j, k);
				if (DEBUG && l > 0) fprintf(stderr, "  remove edge %d-%d\n", k, l);
				Mv[j] = k, Mv[k] = j;
				j = l;
			}
		}
	return c;
}

void WriteTest() {
	printf("%d %d\n", N, M);
	int i, j;
	for (i = 1; i <= N; i++)
		for (j = 1; j <= nv[i]; j++)
			if (i < v[i][j])
				printf("%d %d\n", i, v[i][j]);
}

int main() {
	//freopen("y.txt", "r", stdin);
	int t, T, win2, i, j;
	scanf("%d", &T);
	for (t = 1; t <= T; t++) {
		ReadInput();
		int c, C = MaxMatching();
		for (win2 = 0, i = 1; i <= N; i++) {
			if (USE_SLOW_ALGO) {
				if ((c = MaxMatching(i)) < C) {
					win2++;
					//fprintf(stderr, "win2=%d i=%d c=%d C=%d\n", win2, i, c, C);
				}
			} else {
				// For every vertex i which is part of the initial maximum matching, try to remove it and check if the matching can be increased. If not, then i occurs in all maximum matchings of the graph. For testing if the matching can be increased after removing the vertex i it is enough to try to find an augmenting path starting from the vertex j, which is the vertex to which i is matched in the initial maximum matching.
				if (!Mv[i]) continue;
				for (j = 1; j <= N; j++)
					if (j != i && (!Mv[j] /*|| Mv[j] == i*/) && FindAugmentingPath(j, i)) {
						if (DEBUG) fprintf(stderr, "[Ans] excl=%d: FindAugmentingPath(%d)=1\n", i, j);
						break;
					}
				if (j > N) {
					win2++;
					//fprintf(stderr, "win2=%d i=%d\n", win2, i);
				}
			}
		}
		printf("%d\n", N - win2);
	}
	return 0;
}