#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 0x3f3f3f3f
#define L_INF 0x7f3f3f3f3f3f3f3f
#define db cout << "debug\n";

using namespace std;
const int Mod = 998244353;
using ll = long long;
namespace Dinic
{
    const int N = 100000 * 4 + 5;
    int n, m; // 点数，边数
    int s, t; // 起点，终点
    int head[N], e[N << 1], ne[N << 1], tot = 1;
    int val[N << 1];
    int cur[N << 1];
    void add(int u, int v, int w)
    {
        // cout << u << ' ' << v << ' ' << w << '\n';
        ne[++tot] = head[u];
        e[tot] = v;
        val[tot] = w;
        head[u] = tot;

        ne[++tot] = head[v];
        e[tot] = u;
        val[tot] = 0;
        head[v] = tot;
    }
    ll dis[N];
    bool bfs()
    {
        // cout << n << ' ' << s << ' ' << t << '\n';
        for (int i = 1; i <= n; i++)
        {
            dis[i] = INF;
        }
        queue<int> q;
        q.push(s);
        dis[s] = 0;
        cur[s] = head[s];
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = head[u]; i; i = ne[i])
            {
                int v = e[i];
                ll w = val[i];
                if (w > 0 && dis[v] == INF)
                {
                    dis[v] = dis[u] + 1;
                    cur[v] = head[v];
                    q.push(v);
                    if (v == t)
                        return true;
                }
            }
        }
        return false;
    }
    int dfs(int u, int sum)
    {
        if (u == t)
            return sum;
        int res = 0;
        for (int i = cur[u]; i; i = ne[i])
        {
            cur[u] = i;
            int v = e[i];
            int w = val[i];
            if (w > 0 && dis[u] + 1 == dis[v])
            {
                int k = dfs(v, min(w, sum));
                if (k == 0)
                    dis[v] = INF;
                val[i] -= k;
                val[i ^ 1] += k;
                res += k;
                sum -= k;
                if (sum <= 0)
                    break;
            }
        }
        return res;
    }
    int getans()
    {
        int ans = 0;
        while (bfs())
        {
            // for (int i = 1; i <= n; i++)
            // {
            //     cout << dis[i] << " \n"[i == n];
            // }
            ans += dfs(s, INF);
        }
        // for (int i = 1; i <= n; i++)
        // {
        //     cout << dis[i] << " \n"[i == n];
        // }
        // cout << ans << '\n';
        return ans;
    }
    // cout << ans << " " << ans2 << '\n';
    void init(int n, int s, int t)
    {
        for (int i = 0; i <= n; i++)
            head[i] = 0;
        Dinic::n = n;
        Dinic::s = s;
        Dinic::t = t;
        tot = 1;
    }
    int bfs2(int s)
    {
        for (int i = 1; i <= n; i++)
            dis[i] = INF;
        queue<int> q;
        q.push(s);
        dis[s] = 0;
        cur[s] = head[s];
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = head[u]; i; i = ne[i])
            {
                int v = e[i];
                ll w = val[i];
                if (w == 0 && dis[v] == INF)
                {
                    dis[v] = dis[u] + 1;
                    cur[v] = head[v];
                    q.push(v);
                }
            }
        }
        int tt = 0;
        for (int i = 1; i <= n; i++)
        {
            // cout << i << ':' << dis[i] << '\n';
            if (dis[i] != INF && dis[i] != 0)
                tt++;
        }
        return tt;
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;
    int s = 2 * n + 1;
    int t = 2 * n + 2;
    Dinic::init(t, s, t);
    for (int i = 1; i <= n; i++)
    {
        Dinic::add(s, i, 1);
        Dinic::add(i + n, t, 1);
    }

    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        Dinic::add(u, v + n, 1);
    }

    int maxflow = Dinic::getans();
    // cout << maxflow << '\n';
    ll ans1 = 0;
    for (int i = 1; i <= n; i++)
    {
        // cout << Dinic::dis[i] << '\n';
        if (Dinic::dis[i] != INF)
            ans1++;
    }
    // cout << ans1 << " " << Dinic::bfs2(t) << '\n';
    cout << ans1 * Dinic::bfs2(t) << '\n';
}
int main()
{
    IOS;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#ifndef ONLINE_JUDGE
    clock_t start_time = clock();
#endif
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
#ifndef ONLINE_JUDGE
    cout << "Used " << (double)(clock() - start_time) << " ms" << endl;
#endif
    return 0;
}