#include<bits/stdc++.h>

constexpr int inf = 1E9;
template<class T>
struct MaxFlow {
    struct _Edge {
        int to;
        T cap;
        _Edge(int to, T cap) : to(to), cap(cap) {}
    };

    int n;
    std::vector<_Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h, gap;

    MaxFlow() {}
    MaxFlow(int n) {
        init(n);
    }

    void init(int n) {
        this->n = n;
        e.clear();
        g.assign(n, {});
        cur.resize(n);
        h.resize(n);
        gap.resize(n+2);
    }

    bool bfs(int s, int t) {
        h.assign(n, -1);
        gap.assign(n+2, 0);
        std::queue<int> que;
        h[s] = 0; gap[h[s]] = 1;
        que.push(s);
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (int i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    gap[h[v]]++;
                    if (v == t) {
                        return true;
                    }
                    que.push(v);
                }
            }
        }
        return false;
    }

    void addEdge(int u, int v, T c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }
    T flow(int s, int t) {
        bfs(s, t);
        T ans = 0;
        auto dfs = [&](auto&&dfs, int u, T f) -> T {
            if (u == t) {
                return f;
            }
            auto r = f;
            for (int &i = cur[u]; i < int(g[u].size()); ++i) {
                const int j = g[u][i];
                auto [v, c] = e[j];
                if (c > 0 && h[v] == h[u] + 1) {
                    auto a = dfs(dfs, v, std::min(r, c));
                    e[j].cap -= a;
                    e[j ^ 1].cap += a;
                    r -= a;
                    if (r == 0) {
                        return f;
                    }
                }
            }
            if(--gap[h[u]] == 0){
                h[s] = n + 1;
            }
            ++gap[++h[u]];
            cur[u] = h[u];
            return f - r;
        };
        while (h[s] < n) {
            cur.assign(n, 0);
            ans += dfs(dfs, s, std::numeric_limits<T>::max());
        }
        return ans;
    }

    std::vector<bool> minCut() {
        std::vector<bool> c(n);
        for (int i = 0; i < n; i++) {
            c[i] = (h[i] != -1);
        }
        return c;
    }

    long long getAns(int N, int s, int t) {
        std::vector<bool> vis_t(N * 2 + 3, false);
        std::queue<int> q;
        int s1 = 0, s2 = 0;
        q.push(s);
        vis_t[s] = true;
        while(!q.empty()) {
            int x = q.front();
            if(x != s && x != t && x <= N) {
                s1++;
            }
            q.pop();
            for(auto i : g[x]) {
                auto [to, cap] = e[i];
                if(cap == 0 || vis_t[to]) {
                    continue;
                }
                vis_t[to] = true;
                q.push(to);
            }
        }
        q = {};
        std::fill(vis_t.begin(), vis_t.end(), false);
        q.push(t);
        vis_t[t] = true;
        while(!q.empty()) {
            int x = q.front();
            if(x != s && x != t && x > N) {
                s2++;
            }
            q.pop();
            for(auto i : g[x]) {
                auto [to, cap] = e[i];
                if(cap == 1 || vis_t[to]) {
                    continue;
                }
                vis_t[to] = true;
                q.push(to);
            }
        }
        return 1ll * s1 * s2;
    }
};
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    std::cin >> T;
    while(T--) {
        int n, m;
        std::cin >> n >> m;
        int s = n * 2 + 1, t = n * 2 + 2;
        MaxFlow<int> g(n * 2 + 3);
        for(int x, y, i = 1; i <= m; i++) {
            std::cin >> x >> y;
            g.addEdge(x, n + y, 1);
        }
        for(int i = 1; i <= n; i++) {
            g.addEdge(s, i, 1);
            g.addEdge(i + n, t, 1);
        }
        g.flow(s, t);
        std::cout << g.getAns(n, s, t) << '\n';
    }

    return 0;
}