#include <iostream>
using namespace std;

int t,ft,r,c,n,k,link[500];
bool map[500][500],cover[500];

void readin()
{
     int i,j;
     cin >> n >> k;
     for (i = 1;i <= n;i++)
     for (j = 1;j <= n;j++)
         map[i][j] = false;
     for (i = 1;i <= k;i++)
     {
         cin >> r >> c;
         map[r][c] = true;
     }
}

bool find(int i)
{
     int k,q;
     for (k = 1;k <= n;k++)
     if ((map[i][k] == true) && (cover[k] == false))
     {
                    q = link[k];
                    link[k] = i;
                    cover[k] = true;
                    if ((q == 0) || (find(q) == true))  return true;
                    link[k] = q;
     }
     return false;
}

void km()
{
     int i,j;
     for (i = 1;i <= n;i++)
         link[i] = 0;
     for (i = 1;i <= n;i++)
     {
         for (j = 1;j <= n;j++)
             cover[j] = false;
         find(i);
     }
}
     
void count()
{
     int i,ans;
     ans = 0;
     for (i = 1;i <= n;i++)
     if (link[i] != 0) ans++;
     cout << ans << endl;
}

int main()
{
    cin >> t;
    for (ft = 1;ft <= t;ft++)
    {
        readin();
        km();
        count();
    }
    return 0;
}