//有向图最小路径覆盖：从某一点出发沿着有向路径，不走回路，能将所有的结点遍历。

#include<iostream>

#include<cstdio>

#include<vector>

#include<set>

using namespace std;

const int MAX_N=;

int match[MAX_N];

bool vis[MAX_N];

set<int> insert;

vector<int> e[MAX_N];

int n,k;

void Init()

{

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

    memset(match, -, sizeof(match));

    insert.clear();

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

    {

        e[i].clear();

    }

    int a, b;

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

    {

        scanf("%d %d", &a, &b);

        insert.insert(a);

        e[a].push_back(b);

    }

}

bool Dfs(int x)

{

    for(int i=; i<e[x].size(); i++)

    {

        int u=e[x][i];

        if(!vis[u])

        {

            vis[u]=;

            if(match[u]==-||Dfs(match[u]))

            {

                match[u]=x;

                return true;

            }

        }

    }

    return false;

}

int Bi_matching()

{

    int ans=;

    set<int>::iterator it;

    for(it=insert.begin(); it!=insert.end(); it++)

    {

        int i=(*it);

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

        if(Dfs(i))

            ans++;

    }

    return ans;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        Init();

        printf("%d\n",n-Bi_matching());//最小路径覆盖=结点数-最小点集覆盖

    }

    return ;

}