#include "bits/stdc++.h"
using namespace std;

#define ll long long
#define MOD ((int) (1e9) + 7)
#define pii pair<int, int>

#define N 100010
#define inf 0x7fffffff

struct Edge {
    int u, v, c, nxt;
    Edge(): u(0), v(0), c(0), nxt(0) {};
    Edge(int u, int v, int c, int nxt): u(u), v(v), c(c), nxt(nxt) {};
};

struct MaxFlow {
    int n, m;

    Edge E[N];
    int h[N], cur[N], dis[N], flow;
    int q[N], ql, qr;
    bool inS[N], inT[N];
    
    void init(int n) {
        this->n = n;
        this->m = 2;

        for (int i = 1; i <= n; ++ i) h[i] = 0;
    }

    void add_edge(int u, int v, int c) {
        E[m] = Edge(u, v, c, h[u]), h[u] = m ++; 
        E[m] = Edge(v, u, 0, h[v]), h[v] = m++;
    }

    bool bfs(int s, int t) {
        for (int i = 1; i <= n; ++ i) dis[i] = inf;

        ql = qr = 0;
        q[qr ++] = s;
        dis[s] = 0, cur[s] = h[s];

        while (ql < qr) {
            int u = q[ql ++];
            for (int i = h[u]; i; i = E[i].nxt) {
                auto [_, v, c, __] = E[i];
                if (c && dis[v] == inf) {
                    dis[v] = dis[u] + 1;
                    cur[v] = h[v];
                    q[qr ++] = v;
                }
            }
        }

        return dis[t] != inf;
    }

    int dfs(int u, int t, int in) {
        if (u == t) return in;
        if (dis[u] >= dis[t]) return 0;

        int out = 0;
        for (int i = cur[u]; i && in > out; i = E[i].nxt) {
            cur[u] = i;
            auto [_, v, c, __] = E[i];
            
            int vout = dfs(v, t, min(in - out, c));
            E[i].c -= vout, E[i^1].c += vout, out += vout;
        }
        return out;
    }

    void go(int s, int t) {
        flow = 0;
        int sflow;
        while (bfs(s, t)) while (sflow = dfs(s, t, inf)) flow += sflow;
    }

    void revisit(int s, int t) {
        for (int i = 1; i <= n; ++ i) inS[i] = inT[i] = 0;

        ql = qr = 0;
        q[qr ++] = s;
        inS[s] = 1;
        while (ql < qr) {
            int u = q[ql ++];
            for (int i = h[u]; i; i = E[i].nxt) {
                auto [_, v, c, __] = E[i];
                if (c && !inS[v]) {
                    q[qr ++] = v;
                    inS[v] = 1;
                }
            }
        }

        ql = qr = 0;
        q[qr ++] = t;
        inT[t] = 1;
        while (ql < qr) {
            int u = q[ql ++];
            for (int i = h[u]; i; i = E[i].nxt) {
                auto [v, _, c, __] = E[i^1];
                if (c && !inT[v]) {
                    q[qr ++] = v;
                    inT[v] = 1;
                }
            }
        }
    } 
} mf;

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        int n, m; cin >> n >> m;
        int s = 2*n+1, t = s+1;

        mf.init(t);
        for (int i = 1; i <= n; ++ i) mf.add_edge(s, i, 1);
        for (int i = n+1; i <= 2*n; ++ i) mf.add_edge(i, t, 1);
        for (int i = 0; i < m; ++ i) {
            int u, v; cin >> u >> v; v += n;
            mf.add_edge(u, v, 1);
        }

        mf.go(s, t);
        mf.revisit(s, t);

        int Us = 0, Vs = 0;
        for (int i = 1; i <= n; ++ i) Us += mf.inS[i];
        for (int i = n+1; i <= 2*n; ++ i) Vs += mf.inT[i];

        cout << 1ll * Us * Vs << '\n';
    }


    return 0;
}