#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<map>

#include<stack>

#include<cmath>

#include<vector>

#include<set>

#include<cstdio>

#include<string>

#include<deque>

using namespace std;

typedef long long LL;

#define eps 1e-8

#define INF 0x3f3f3f3f

#define maxn 5005

struct node{

    int v,next;

}edge1[maxn**],edge2[maxn**];

int head1[maxn],dfn[maxn],low[maxn],s[maxn],color[maxn];

int head2[maxn],pre[maxn*];

bool vis[maxn*];

int top,cnt1,time,color_num;

int cnt2,ans;

int n,m,k,t;

void init()

{

    memset(head1,-,sizeof(head1));

    memset(dfn,,sizeof(dfn));

    memset(vis,false,sizeof(vis));

    memset(pre,-,sizeof(pre));

    memset(head2,-,sizeof(head2));

    cnt1=time=color_num=top=;

    cnt2=ans=;

}

void addedge1(int u,int v)//第一次建图添加边

{

    edge1[++cnt1].v=v;

    edge1[cnt1].next=head1[u];

    head1[u]=cnt1;

}

void addedge2(int u,int v)//第二次建图添加边

{

    edge2[++cnt2].v=v;

    edge2[cnt2].next=head2[u];

    head2[u]=cnt2;

}

void DFS(int u)//缩点(染色)

{

    low[u]=dfn[u]=++time;

    vis[u]=true;

    s[top++]=u;

    for(int i=head1[u];i!=-;i=edge1[i].next)

    {

        int v=edge1[i].v;

        if(!dfn[v])

        {

            DFS(v);

            low[u]=min(low[u],low[v]);

        }

        else if(vis[v])

        low[u]=min(low[u],dfn[v]);

    }

    if(low[u]==dfn[u])

    {

        color_num++;

        int v;

        do{

            v=s[--top];

            vis[v]=false;

            color[v]=color_num;

        }while(u!=v);

    }

}

void tarjan()

{

    for(int i=;i<=n;i++)

    {

        if(!dfn[i])

        DFS(i);

    }

}

void rebuild()

{

    for(int i=;i<=n;i++)

    {

        for(int j=head1[i];j!=-;j=edge1[j].next)

        {

            int v=edge1[j].v;

            int a=color[i];

            int b=color[v];

            if(a!=b)

            addedge2(a,b);//建一个二分图

            //最小路径覆盖就是点数减最大匹配，注意前提是图里面无环，所以要先缩点

        }

    }

}

bool hungry_DFS(int u)//求最大匹配

{

    for(int i=head2[u];i!=-;i=edge2[i].next)

    {

        int v=edge2[i].v;

        if(vis[v])

        continue;

        vis[v]=true;

        if(pre[v]==-||hungry_DFS(pre[v]))

        {

            pre[v]=u;

            return true;

        }

    }

    return false;

}

void hungry()

{

    for(int i=;i<=color_num;i++)

    {

        memset(vis,false,sizeof(vis));

        if(hungry_DFS(i))

        ans++;

    }

    printf("%d\n",color_num-ans);//注意这里是缩点之后的点数减最大匹配数

}

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        init();

        int u,v;

        for(int i=;i<=m;i++)

        {

            scanf("%d%d",&u,&v);

            addedge1(u,v);//第一次建图

        }

        tarjan();//缩点

        rebuild();//第二次建图

        hungry();//求最大匹配

    }

    return ;

}