#include<iostream>
#define SIZE 120
using namespace std;
int tcase,n,m,x,y;
int t[SIZE];
bool v[SIZE],a[SIZE][SIZE];
bool find(int x)
{
    for(int i=0;n-i>0;i++)
    {
        if(v[i]==false&&a[x][i]==true)
        {
            v[i]=true;
            if(t[i]==-1||find(t[i]))
            {
                t[i]=x;
                return true;
            }
        }
    }
    return false;
}
int findMatch(void)
{
    int count=0;
    for(int i=0;n-i>0;i++)
    {
        memset(v,false,sizeof(v));
        if(find(i)) count++;
    }
    return count;
}
int main()
{
    scanf("%d",&tcase);while(tcase--)
    {
        memset(t,-1,sizeof(t));
        memset(a,false,sizeof(a));
        scanf("%d %d",&n,&m);
        for(int i=0;m-i>0;i++)
        {
            scanf("%d %d",&x,&y);
            a[x-1][y-1]=true;
        }
        printf("%d\n",n-findMatch());
    }
    return 0;
}