#include <bits/stdc++.h>

#pragma - Ofast

// #define int ll
// using ll = long long;

const int inf = 1e9;

using namespace std;

namespace FAST
{
    char buf[1 << 20], *p1, *p2;
    char gc() { return p1 == p2 ? p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), (p1 == p2) ? EOF : *p1++ : *p1++; }
    inline int read(int f = 1, char c = gc(), int x = 0)
    {
        while (c < '0' || c > '9')
            f = (c == '-') ? -1 : 1, c = gc();
        while (c >= '0' && c <= '9')
            x = x * 10 + c - '0', c = gc();
        return f * x;
    }
}
using FAST::read;

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;
            }
        }
        if (ret == 0)
            dep[u] = -1;
        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];

MF graph(200010);

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;
    __ = read();

    while (__--)
        solve();

    return 0;
}

void solve()
{
    n = read();
    m = read();
    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;

    graph.n = ed;
    graph.e.clear();
    for (int i = 1; i <= ed; i++)
    {
        graph.fir[i] = 0;
        graph.cur[i] = 0;
        graph.cnt = 1;
    }

    for (int i = 1; i <= m; i++)
    {
        int u, v;
        u = read();
        v = read();
        graph.addedge(u, v + n, 1);
    }
    for (int i = 1; i <= n; i++)
    {
        graph.addedge(st, i, 1);
        graph.addedge(i + n, ed, 1);
    }

    graph.maxflow(st, ed);

    for (int i = 1; i <= ed; i++)
        vis[i] = 0;
    vis[st] = 1;
    int cntl = dfs(st, graph, 1);
    for (int i = 1; i <= ed; i++)
        vis[i] = 0;
    vis[ed] = 1;
    int cntr = dfs(ed, graph, 2);

    cout << (long long)cntl * (long long)cntr << '\n';
}

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

    for (int i = g.fir[x]; ~i; i = g.e[i].nxt)
    {
        if (mode == 1)
        {
            if (g.e[i].cap - g.e[i].flow < 1 || g.e[i].v == 2 * n + 2)
                continue;
        }
        else
        {
            if (g.e[i].cap - g.e[i].flow > 0 || g.e[i].v == 2 * n + 1)
                continue;
        }

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

        if (vis[u])
            continue;

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

    return res;
}