//Hungary

#include<bits/stdc++.h>

using namespace std;

#define N 50

int useif[N];   //记录y中节点是否使用 0表示没有访问过，1为访问过

int link[N];   //记录当前与y节点相连的x的节点

int mat[N][N]; //记录连接x和y的边，如果i和j之间有边则为1，否则为0

int gn, gm;   //二分图中x和y中点的数目

int can(int t) {

        int i;

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

                if (useif[i] ==  && mat[t][i]) {

                        useif[i] = ;

                        if (link[i] == - || can(link[i])) {

                                link[i] = t;

                                return ;

                        }

                }

        }

        return ;

}

int MaxMatch() {

        int i, num;

        num = ;

        memset(link, 0xff, sizeof(link));

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

                memset(useif, , sizeof(useif));

                if (can(i)) {

                        num++;

                }

        }

        return num;

}

int main() {

        int TCASE;

        scanf("%d", &TCASE);

        while (TCASE--) {

                int n, k;

                int u, v;

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

                gn = gm = n;

                memset(mat, , sizeof(mat));

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

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

                        mat[u][v] = ;

                }

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

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

                                mat[i][j] = mat[i][j] ^ ;

                        }

                }

                int ans = n * ;

                ans -= MaxMatch();

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

        }

}