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

using ll = long long;
using ld = long double;

#define pb push_back
#define si(x) int(x.size())
#define all(x) x.begin(), x.end()
#define fi first
#define se second

struct Dinic {
    struct Edge {
        int to, rev;
        ll c, oc;
        ll flew() { return max(oc - c, 0LL); }
    };
    vector <int> lvl, ptr, q;
    vector<vector<Edge>> adj;
    Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}
    void addEdge(int a, int b, ll c, ll rcap = 0) {
        adj[a].push_back({b, adj[b].size(), c, c});
        adj[b].push_back({a, adj[a].size() - 1, rcap, rcap});
    }
    ll dfs(int v, int t, ll f) {
        if (v == t || !f) return f;
        for (int& i = ptr[v]; i < adj[v].size(); i++) {
            Edge& e = adj[v][i];
            if (lvl[e.to] == lvl[v] + 1)
                if (ll p = dfs(e.to, t, min(f, e.c))) {
                    e.c -= p, adj[e.to][e.rev].c += p;
                    return p;
                }
        }
        return 0;
    }
    ll calc(int s, int t) {
        ll flow = 0; q[0] = s;
        for(int L=0; L<=30; L++) do {
            lvl = ptr = vector <int> (q.size());
            int qi = 0, qe = lvl[s] = 1;
            while (qi < qe && !lvl[t]) {
                int v = q[qi++];
                for (Edge e : adj[v])
                    if (!lvl[e.to] && e.c >> (30 - L))
                        q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;
            }
            while (ll p = dfs(s, t, LLONG_MAX)) flow += p;
        } while (lvl[t]);
        return flow;
    }
    bool leftOfMinCut(int a) { return lvl[a] != 0; }
};

const int N = 200000;
int n;

bool visited[N+5];

int levo, desno;

void dfs1(int v, Dinic &flw){
    if(1 <= v && v <= n) levo++;
    visited[v] = 1;
    for(auto c : flw.adj[v]){
        int u = c.to;
        if(c.c <= 0 || visited[u]) continue;
        dfs1(u, flw);
    }
}

void dfs2(int v, Dinic &flw){
    if(n + 1 <= v && v <= 2*n) desno++;
    visited[v] = 1;
    for(auto dc : flw.adj[v]){
        int u = dc.to;
        auto c = flw.adj[u][dc.rev];
        if(c.c <= 0 || visited[u]) continue;
        dfs2(u, flw);
    }
}

void solve(){
    int m;
    cin >> n >> m;
    Dinic flw(2 + 2*n);
    for(int i=1; i<=m; i++){
        int u, v;
        cin >> u >> v;
        flw.addEdge(u, n + v, 1);
    }
    for(int i=1; i<=n; i++){
        flw.addEdge(0, i, 1);
        flw.addEdge(n + i, 2*n + 1, 1);
    }
    flw.calc(0, 2*n + 1);
    levo = 0, desno = 0;
    for(int i=0; i<=2*n+1; i++) visited[i] = 0;
    dfs1(0, flw);
    dfs2(2*n + 1, flw); 
    cout << 1LL*levo*desno << "\n";
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}