#include<iostream>

#include<cstring>

using namespace std;

const int maxn=;

int g[maxn][maxn];

int uN,vN;

int linker[maxn];

bool used[maxn];

bool dfs(int u)

{

    for(int v = ; v < vN; v++)

        if(g[u][v] && !used[v])

        {

            used[v] = true;

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

            {

                linker[v] = u;

                return true;

            }

        }

    return false;

}

int hungary()

{

    int res = ;

    memset(linker,-,sizeof(linker));

    for(int u = ; u < uN; u++)

    {

        memset(used,false,sizeof(used));

        if(dfs(u))res++;

    }

    return res;

}

int main()

{

    int n,m,t;

    cin>>t;

    while (t--)

    {

        cin>>n>>m;

        memset(g,,sizeof(g));

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

        {

            int u,v;

            cin>>u>>v;

            g[u-][v-]=;

        }

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

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

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

                    if (g[i][k] && g[k][j]) g[i][j]=;

        uN=vN=n;

        cout<<n-hungary()<<endl;

    }

    return ;

}