#include<stdio.h>

#include<iostream>

#include<math.h>

#include<string.h>

#include<set>

#include<map>

#include<list>

#include<math.h>

#include<queue>

#include<algorithm>

using namespace std;

typedef long long LL;

#define INF 0x7fffffff

#define mem(a,x) memset(a,x,sizeof(a))

int mon1[]= {,,,,,,,,,,,,};

int mon2[]= {,,,,,,,,,,,,};

int dir[][]= {{,},{,-},{,},{-,}};

int getval()

{

    int ret();

    char c;

    while((c=getchar())==' '||c=='\n'||c=='\r');

    ret=c-'';

    while((c=getchar())!=' '&&c!='\n'&&c!='\r')

        ret=ret*+c-'';

    return ret;

}

#define max_v 5005

int dfn[max_v];

int low[max_v];

int vis[max_v];

int stk[max_v];

int color[max_v];

vector<int> G[max_v];

vector<int> G2[max_v];

int n,m;

int sig,cnt,sp;

int link[max_v];

int match[max_v];

void init()

{

    mem(dfn,);

    mem(low,);

    mem(vis,);

    mem(stk,);

    mem(color,);

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

    {

        G[i].clear();

        G2[i].clear();

    }

    sig=;

    cnt=;

    sp=-;

}

int tarjan(int u)

{

    vis[u]=;

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

    stk[++sp]=u;

    for(int j=;j<G[u].size();j++)

    {

        int v=G[u][j];

        if(vis[v]==)

            tarjan(v);

        if(vis[v]==)

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

    }

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

    {

        sig++;

        do

        {

            color[stk[sp]]=sig;

            vis[stk[sp]]=-;

        }while(stk[sp--]!=u);

    }

}

int dfs(int u)

{

    for(int j=;j<G2[u].size();j++)

    {

        int v=G2[u][j];

        if(vis[v]==)

        {

            vis[v]=;

            if(match[v]==-||dfs(match[v]))

            {

                match[v]=u;

                return ;

            }

        }

    }

    return ;

}

int max_match()//匈牙利算法

{

    mem(match,-);

    int ans=;

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

    {

        mem(vis,);

        if(dfs(i))

            ans++;

    }

    return ans;

}

int main()

{

    int t;

    cin>>t;

    int x,y;

    while(t--)

    {

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

        init();

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

        {

            scanf("%d %d",&x,&y);

            if(count(G[x].begin(),G[x].end(),y)==)//重边

                G[x].push_back(y);

        }

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

        {

            if(vis[i]==)

                tarjan(i);

        }

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

        {

            for(int j=;j<G[i].size();j++)

            {

                if(color[i]!=color[G[i][j]])

                {

                    if(count(G2[color[i]].begin(),G2[color[i]].end(),color[G[i][j]])==)//重边

                        G2[color[i]].push_back(color[G[i][j]]);

                }

            }

        }

        printf("%d\n",sig-max_match());//最小不相交路径覆盖=新图点数-最大二分匹配数

    }

    return ;

}

/*

题目意思：

现在有n个点，m条边的有向图，要求划分的区域最少

规则如下：

1.可以互相到达的点必须属于一个区域

2.u可以到v或者v可以到v，即一个区域内任意两点u,v,必须存在路径从u->v或者从v->u

3.一个点只能属于一个区域

4.所有点都应该被划分

分析：

可以互相到达的点肯定是属于一个强连通分量的，所以利用tarjan将属于同一个强连通分量的点缩成一个点

得到新图，现在新图是一个DAG图，有向无环图

最小路径的定义：在一个有向图中，找出最少的路径，使得这些路径经过了所有的点

对照一下题目：一个区域其实就是一条路径

最少的区域数目就是最少的路径数目

所以题目转换成最小不相交的路径覆盖，注意：不相交的路径，疑问一个点只能属于一个区域

最小不相交路径覆盖=点数-最大二分匹配

所以对得到的新图，求一遍最大二分匹配就好

最大二分匹配用匈牙利算法写

gameover!

*/