#include<iostream>
using namespace std;
bool str[121][121];
int ans[1000];
int strnum,lnum;
void in()
{
	cin>>strnum;
	cin>>lnum;
	int a,b;
	for(int i=0;i<lnum;i++)
	{
		cin>>a>>b;
		str[a][b]=1;
	}
}
int bipartitl()//匈牙利算法,根据师兄的模板写的
{
	int q[121],prev[121],t,r;//prev存储交错链和,同时表示右边的点是否用过
	int vm1[121],vm2[121];//二部图的两边
	int n=0;
	int i,j,x;
	for(i=1;i<=strnum;i++)
	{
		vm1[i]=-1;
		vm2[i]=-1;
	}
	for(i=1;i<=strnum;i++)
	{
		if(vm1[i]!=-1) continue;
		memset(q,0,sizeof(q));
		t=r=0;
		for(j=1;j<=strnum;j++) prev[i]=-2;
		for(j=1;j<=strnum;j++)
		{
			if(str[i][j])
			{
				prev[j]=-1;
				q[r++]=j;
			}
		}
		while(t!=r)
		{
			x=q[t];
			if(vm2[x]==-1) break;
			t++;
			for(j=1;j<=strnum;j++)
				if(prev[j]==-2&&str[vm2[x]][j])
				{
					prev[j]=x;
					q[r++]=j;
				}
		}
		if(t==r) continue;
		while(prev[x]>-1)
		{
			vm1[vm2[prev[x]]]=x;
			vm2[x]=vm2[prev[x]];
			x=prev[x];
		}	
		vm1[i]=x;
		vm2[x]=i;
		n++;
	}
	return n;
}
int main()
{
	int casnum;
	cin>>casnum;
	for(int cas=1;cas<=casnum;cas++)
	{
		memset(str,0,sizeof(str));
		in();
		ans[cas-1]=strnum-bipartitl();
	}
	for(int k=0;k<casnum;k++)
		cout<<ans[k]<<endl;
	return 0;
}
谢谢各位了