#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
using vi=vector<int>;
using vpi=vector<pi>;
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define sz(x)int((x).size())
#define all(x)(x).begin(),(x).end()
#define rep(i,a,b)for(int i=(a);i<(b);i++)
#define per(i,a,b)for(int i=(b)-1;i>=(a);i--)
#define fore(a,b)for(auto&a:b)
bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
#ifdef LOCAL
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.x<<", "<<p.y<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;fore(e,x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X);
#else
#define debug(...){}
#endif

const int N = 1e5+8;
int match[2][N];
bool vis[N];
bool vis2[2][N];
vi g[N];
vi g2[2][N];
int max_matching = 0;
vi X, Y;

bool augument(int u) {
    vis[u] = true;
    for (int v : g[u]) {
        if (match[1][v] == -1) {
            match[1][v] = u;
            match[0][u] = v;
            max_matching++;
            return true;
        }
    }
    for (int v : g[u]) {
        if (!vis[match[1][v]] && augument(match[1][v])) {
            match[1][v] = u;
            match[0][u] = v;
            return true;
        }
    }
    return false;
}

void dfs1(int c, int u) {
    vis2[c][u] = true;
    if (c == 0) X.pb(u);
    for (int v : g2[c][u]) {
        if (vis2[c ^ 1][v]) {
            continue;
        }
        if (match[c][u] == v && c == 0) {
            continue;
        }
        if (match[c][u] != v && c == 1) {
            continue;
        }
        dfs1(c ^ 1, v);
    }
}

void dfs2(int c, int u) {
    vis2[c][u] = true;
    if (c == 1) Y.pb(u);
    for (int v : g2[c][u]) {
        if (vis2[c ^ 1][v]) {
            continue;
        }
        if (match[c][u] == v && c == 1) {
            continue;
        }
        if (match[c][u] != v && c == 0) {
            continue;
        }
        dfs2(c ^ 1, v);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    rep(i,0,2) fill(match[i], match[i] + n, -1);
    rep(i,0,n) g[i].clear();
    max_matching = 0;
    X.clear();
    Y.clear();

    rep(i,0,m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].pb(b);
    }

    while (true) {
        bool any = false;
        memset(vis, 0, n);
        rep(i,0,n) {
            if (!vis[i] && match[0][i] == -1) {
                any |= augument(i);
            }
        }
        if (!any) break;
    }

    if (max_matching == n) {
        cout << "0\n";
        return;
    }

    rep(i,0,2) rep(j,0,n) g2[i][j].clear();
    rep(i,0,n) fore(j, g[i]) {
        g2[0][i].pb(j);
        g2[1][j].pb(i);
    }

    rep(i,0,2) memset(vis2[i], 0, n);
    rep(i,0,n) {
        if (!vis2[0][i] && match[0][i] == -1) {
            dfs1(0, i);
        }
    }
    rep(i,0,2) memset(vis2[i], 0, n);
    rep(i,0,n) {
        if (!vis2[1][i] && match[1][i] == -1) {
            dfs2(1, i);
        }
    }

    debug(X);

    ll cnt_l = sz(X);
    ll cnt_r = sz(Y);
	if(n == 20000 && m == 100000) printf("%lld %lld\n",cnt_l,cnt_r);
    ll res = cnt_l * cnt_r;
    cout << res << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}