include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

using namespace std;

#define INF 0x3f3f3f3f

#define MM(x) memset(x,0,sizeof(x))

#define MMINF(x) memset(x,INF,sizeof(x))

typedef long long LL;

const double PI=acos(-1.0);

const int N=20010;

struct info

{

    int to;

    int pre;

}E[N];

int head[N],cnt;

int match[N],vis[N];

void init()

{

    memset(head,-1,sizeof(head));

    cnt=0;

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

}

void add(int s,int t)

{

    E[cnt].to=t;

    E[cnt].pre=head[s];

    head[s]=cnt++;

}

int dfs(int u)

{

    for (int i=head[u]; i!=-1; i=E[i].pre)

    {

        int v=E[i].to;

        if(!vis[v])//没被访问过

        {

            vis[v]=1;//标记访问

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

            //若没之前被匹配过或之后可以放到增广路里就合法

            {

                match[v]=u;//路径交换取反

                match[u]=v;//路径交换取反

                return 1;//成功找到增广路

            }

        }

    }

    return 0;

}

int main(void)

{

    int tcase,i,a,b,n,k;

    scanf("%d",&tcase);

    while (tcase--)

    {

        init();

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

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

        {

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

            add(a,b+n);

        }

        int r=0;

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

        {

            if(match[i]==-1)

            {

                MM(vis);

                if(dfs(i))//这个点出发找到增广路

                    r++;

            }

        }

        printf("%d\n",r);

    }

    return 0;

}