/*
题意：一个有n个路口和m条单项的的街道，无环图，要派一些伞兵去镇守成寿寺，要到达所有路口，只要有伞兵到达就可，
每个伞兵从降落的那个路口可以去沿着街道去其他路口。求最少要几个伞兵可以镇守整个路口 。
思路：二分图最小点覆盖，用最少的点去覆盖所有边=最大匹配数
*/
#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
vector<int>map[505];
int boy [501];
int vis[501];
int n,k;
int dfs(int x)
{
for(int i=0;i<map[x].size();i++)
{ int y=map[x][i];
if(vis[y]==0)
{
vis[y]=1;
if(boy[y]==0||dfs(boy[y]))
{
boy[y]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
map[i].clear();
}
for(int i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
map[x].push_back(y);
}
int count=0;
memset(boy,0,sizeof(boy));
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i)) count++;
}
printf("%d\n",n-count);
}
return 0;
}
