#include<cstdio>

#include<cstring>

#include<stack>

#include<cstdlib>

#include<queue>

#include<memory.h>

#include<algorithm>

#include<vector>

#include<iostream>

using namespace std;

const int maxn=;

vector<int>G[maxn];

vector<int>G2[maxn];

vector<int>S;

vector<int>Map[maxn];

int scc[maxn],vis[maxn],n,m,scc_cnt,ans;

int link[maxn];

void _update(){

    for(int i=;i<=n;i++) G[i].clear();

    for(int i=;i<=n;i++) G2[i].clear();

    memset(link,,sizeof(link));

    memset(vis,,sizeof(vis));

    memset(scc,,sizeof(scc));

    S.clear();

    ans=scc_cnt=;

}

void _dfs1(int v){

    if(vis[v]) return ;

    vis[v]=;

    int L=G[v].size();

    for(int i=;i<L;i++)_dfs1(G[v][i]);

    S.push_back(v);

    return ;

}

void _dfs2(int v){

    if(scc[v]) return ;

    scc[v]=scc_cnt;

    int L=G2[v].size();

    for(int i=;i<L;i++) _dfs2(G2[v][i]);

}

void _kosaraju()

{

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

    for(int i=n-;i>=;i--) {

        if(!scc[S[i]]) {

            scc_cnt++;

            Map[scc_cnt].clear();

            _dfs2(S[i]);

         }

    }

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

    {

        int L=G[i].size();

        for(int j=;j<L;j++){

            if(scc[i]!=scc[G[i][j]]){

               Map[scc[i]].push_back(scc[G[i][j]]);

            }

        }

    }

}

bool _find(int v){

    int L=Map[v].size();

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

    {

        if(!vis[Map[v][i]]){

            vis[Map[v][i]]=;

            if(!link[Map[v][i]]||_find(link[Map[v][i]])){

                link[Map[v][i]]=v;

                return true;

            }

        }

    }

    return false;

}

int main()

{

    int T,i,j,u,v;

    scanf("%d",&T);

    while(T--){

        _update();

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

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

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

            G[u].push_back(v);

            G2[v].push_back(u);

        }

        _kosaraju();

        for(i=;i<=scc_cnt;i++){

            memset(vis,,sizeof(vis));

            if(_find(i)) {

              ans++;

            }

        }

        printf("%d\n",scc_cnt-ans);//以Map图位对象，不是n

    }

    return ;

}