#include <bits/stdc++.h>
#define R(x) x = read()
#define int long long
using namespace std;
inline int read(){
	int res=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=getchar();}
	return res*f;
}
inline void P(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        P(x / 10);
        x %= 10;
    }
    putchar(x + '0');
}
int T,n,m,s,t;
int len,fir[5550];
struct b {
	int to,nxt,w;
} v[400100];
void add(int x,int y,int w) {
	++len;
	v[len].to=y;
	v[len].nxt=fir[x];
	v[len].w=w;
	fir[x]=len;
}
struct DINIC{
	const int inf=1e17;
	int d[114514]
	   ,fir2[11451];//当前弧优化 
	int bfs(){
		queue<int> q;
		q.push(s);
		memset(d,-1,sizeof(d));
		d[s]=1;
		while(!q.empty()){
			int nq=q.front();q.pop();
	//		P(nq);SPACE
			if(nq==t)break;
			for(int i=fir2[nq];i;fir2[nq]=i=v[i].nxt){
				if(v[i].w<=0)continue;
				d[v[i].to]=d[nq]+1;
				q.push(v[i].to);
			}
		}
	//	ENDL
		return d[t]^(-1);
	}
	int dfs(int u,int val){
		if(u==t||!val)return val;
		int tmp=0;
		for(int i=fir2[u];i;fir2[u]=i=v[i].nxt){
			if((d[v[i].to]^(1+d[u]))||v[i].w<=0)continue;
			int cut=dfs(v[i].to,min(val,v[i].w));
			v[i].w-=cut;
			v[i^1].w+=cut;
			val-=cut;
			tmp+=cut;
			if(!val)break;
		}
		if(!tmp)d[u]=-1;
		return tmp;
	}

	int dinic(){
		int mincut=0;
		memcpy(fir2,fir,sizeof(fir));
		while(bfs()){
			memcpy(fir2,fir,sizeof(fir));
			mincut+=dfs(s,inf);
			memcpy(fir2,fir,sizeof(fir));
		}
		return mincut;
	}	
}_dinic_;
signed main() {
	R(T);
	while(T--) {
		len=1;
		memset(fir,0,sizeof(fir));
		R(n);
		R(m);
		s=n+n+m+n+1;
		t=n+n+m+n+2;
		for(int i=1; i<=n; i++) {
//			add(i,i+n,1);
//			add(i+n,i,0);
			add(s,i,1);
			add(i,s,0);
			add(i+n,t,1);
			add(t,i+n,0);
		}
		for(int i=1; i<=m; i++) {
			int u,v;
			R(u);
			R(v);
			add(u,v+n,1);
			add(v+n,u,0);
		}
		P(n-_dinic_.dinic());
		putchar('\n');
	}
	return 0;
}
/*
2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3
*/