#include <stdio.h>
#include <string.h>
#define size 150
int g[size][size];
int used[size];
int match[size];
int n,m;
int dfs(int x)
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(!used[i]&&g[x][i])
		{
			used[i]=1;
			if(match[i]==-1||dfs(match[i]))
			{
				match[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int cases,i,a,b,res;
	scanf("%d",&cases);
	while(cases--)
	{
		scanf("%d",&n);
		scanf("%d",&m);
		memset(g,0,sizeof(g));
		memset(match,-1,sizeof(match));
		for(i=1;i<=m;i++)
		{
			scanf("%d %d",&a,&b);
			g[a][b]=1;
		}
		res=0;
		for(i=1;i<=n;i++)
		{
			memset(used,0,sizeof(used));
			if(dfs(i))
				res++;
		}
		printf("%d\n",n-res);
	}
	return 1;
}