#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;
    Edge(): u(0), v(0), c(0) {};
    Edge(int u, int v, int c): u(u), v(v), c(c) {};
};

struct MaxFlow {
    int n, m;
    
    vector<Edge> E;
    vector<int> G[N];

    int cur[N], dis[N], flow, inS[N], inT[N];
    
    void init(int n) {
        this->n = n;
        this->m = 0;
        E.clear();
        for (int i = 1; i <= n; ++ i) G[i].clear();
    }

    void add_edge(int u, int v, int c) {
        E.emplace_back(u, v, c);
        E.emplace_back(v, u, 0);
        G[u].emplace_back(m ++);
        G[v].emplace_back(m ++);
    }

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

        queue<int> q; q.push(s);
        dis[s] = 0, cur[s] = 0;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto e : G[u]) {
                auto [_, v, c] = E[e];
                if (c && dis[v] == inf) {
                    dis[v] = dis[u] + 1;
                    cur[v] = 0;
                    q.push(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 < G[u].size() && in > out; ++ i) {
            cur[u] = i;

            int e = G[u][i];
            auto [_, v, c] = E[e];
            
            int vout = dfs(v, t, min(in - out, c));
            E[e].c -= vout, E[e^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;
        queue<int> q; q.push(s);
        inS[s] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto e : G[u]) {
                auto [_, v, c] = E[e];
                if (c && !inS[v]) {
                    q.push(v);
                    inS[v] = 1;
                }
            }
        }

        q.push(t);
        inT[t] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto e : G[u]) {
                auto [v, _, c] = E[e^1];
                if (c && !inT[v]) {
                    q.push(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;
}