#include<stdio.h>
#include<string.h>
#include<vector>
#include<string>
#include<iostream>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
using namespace std;
int dfn[5050],low[5050],ins[5050],head[5050],belong[5050],stack[5050],link[5050];
int cnt,top,taj,time,n,m;
vector<int>vt[5050];
struct s
{
	int u,v,next;
}edge[100010*2];
void init()
{
	cnt=top=taj=time=0;
	memset(belong,-1,sizeof(belong));
	memset(ins,0,sizeof(ins));
	memset(low,-1,sizeof(low));
	memset(dfn,-1,sizeof(dfn));
	memset(head,-1,sizeof(head));
	memset(stack,0,sizeof(stack));
}
void add(int u,int v)
{
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
void tarjin(int u)
{
	dfn[u]=low[u]=time++;
	stack[top++]=u;
	ins[u]=1;
	for(int i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].v;
		if(dfn[v]==-1)
		{
			tarjin(v);
			low[u]=min(low[u],low[v]);
		}
		else
			if(ins[v])
				low[u]=min(dfn[v],low[u]);
	}
	if(dfn[u]==low[u])
	{
		taj++;
		int now;
		do
		{
			now=stack[--top];
			belong[now]=taj;
			ins[now]=0;
		}while(u!=now);
	}
}
int dfs(int u)
{
	for(int i=0;i<vt[u].size();i++)
	{
		int v=vt[u][i];
		if(!ins[v])
		{
			ins[v]=1;
			if(link[v]==-1||dfs(link[v]))
			{
				link[v]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int i;
		init();
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++)
			vt[i].clear();
		while(m--)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v);
		}
		for(i=1;i<=n;i++)
		{
			if(dfn[i]==-1)
			{
				tarjin(i);
			}
		}
		for(i=0;i<cnt;i++)
		{
			int u=edge[i].u;
			int v=edge[i].v;
			if(belong[u]!=belong[v])
			{
				vt[belong[u]].push_back(belong[v]);
			//	printf("%d %d %d %d\n",u,v,belong[u],belong[v]);
			}
		}
		memset(link,-1,sizeof(link));
		int ans=0;
		for(i=1;i<=taj;i++)
		{
			memset(ins,0,sizeof(ins));
			if(dfs(i))
				ans++;
		}
		printf("%d\n",taj-ans);
	}
}