#include <bits/stdc++.h>

#define int ll
using ll = long long;

const int inf = 1e18;

using namespace std;

struct MF
{
    struct edge
    {
        int v, nxt, cap, flow;
    };

    vector<edge> e;
    vector<int> fir, dep, cur;
    int cnt;

    int n;

    MF(int node)
    {
        fir.resize(node + 5);
        dep.resize(node + 5);
        cur.resize(node + 5);
        n = node;
        cnt = 0;
        for (int i = 0; i <= n; i++)
        {
            fir[i] = ~fir[i];
        }
    }

    void addedge(int from, int to, int w)
    {
        e.push_back({to, fir[from], w, 0});
        fir[from] = cnt++;
        e.push_back({from, fir[to], 0, 0});
        fir[to] = cnt++;
    }

    bool bfs(int st, int ed)
    {
        queue<int> q;
        for (int i = 0; i <= n; i++)
            dep[i] = 0;

        dep[st] = 1;
        q.push(st);
        while (q.size())
        {
            int u = q.front();
            q.pop();
            for (int i = fir[u]; ~i; i = e[i].nxt)
            {
                // cerr << "///\n";
                int v = e[i].v;
                if ((!dep[v]) && (e[i].cap > e[i].flow))
                {
                    dep[v] = dep[u] + 1;
                    q.push(v);
                }
            }
        }
        return dep[ed];
    }

    int dfs(int u, int flow, int ed)
    {
        if ((u == ed) || (!flow))
            return flow;

        int ret = 0;
        for (int &i = cur[u]; ~i; i = e[i].nxt)
        {
            int v = e[i].v, d;
            if ((dep[v] == dep[u] + 1) &&
                (d = dfs(v, min(flow - ret, e[i].cap - e[i].flow), ed)))
            {
                ret += d;
                e[i].flow += d;
                e[i ^ 1].flow -= d;
                if (ret == flow)
                    return ret;
            }
        }
        return ret;
    }

    int maxflow(int st, int ed)
    {
        int res = 0;
        while (bfs(st, ed))
        {
            for (int i = 0; i <= n; i++)
                cur[i] = fir[i];
            res += dfs(st, inf, ed);
            // cerr << res << '\n';
        }

        return res;
    }
};

int n, m;
bool vis[200010];
int l[100010];
int r[100010];

int dfs(int x, MF &g, int mode);
void solve();

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int __ = 1;
    cin >> __;

    while (__--)
        solve();

    return 0;
}

void solve()
{
    cin >> n >> m;
    int st, ed;
    for (int i = 1; i <= n; i++)
    {
        l[i] = i;
        r[i] = i + n;
    }
    st = n * 2 + 1;
    ed = n * 2 + 2;

    MF graph(ed);

    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        graph.addedge(l[u], r[v], 1);
    }
    for (int i = 1; i <= n; i++)
    {
        graph.addedge(st, l[i], 1);
        graph.addedge(r[i], ed, 1);
    }

    graph.maxflow(st, ed);

    // MF lft(ed);
    // for (int i = 1; i <= ed; i++)
    // {
    //     for (int j = graph.fir[i]; ~j; j = graph.e[j].nxt)
    //     {
    //         if (graph.e[j].flow >= graph.e[j].cap || graph.e[j].cap <= 0)
    //             continue;
    //         int from = i, to = graph.e[j].v;
    //         lft.addedge(from, to, 1);
    //     }
    // }

    for (int i = 1; i <= ed; i++)
        vis[i] = 0;
    int cntl = dfs(st, graph, 1);
    int cntr = 0;
    for (int i = r[1]; i <= r[n]; i++)
    {
        for (int j = graph.fir[i]; ~j; j = graph.e[j].nxt)
        {
            if (graph.e[j].v == ed && graph.e[j].flow < graph.e[j].cap)
                cntr++;
        }
    }

    cout << cntl * cntr << '\n';
}

int dfs(int x, MF &g, int mode)
{
    int res = 0;
    if (mode == 1 && l[1] <= x && x <= l[n])
        res++;
    if (mode == 2 && r[1] <= x && x <= r[n])
        res++;

    for (int i = g.fir[x]; ~i; i = g.e[i].nxt)
    {
        if (g.e[i].flow >= g.e[i].cap)
            continue;

        int u = g.e[i].v;

        if (vis[u])
            continue;

        vis[u] = 1;
        res += dfs(u, g, mode);
    }

    return res;
}