#include <bits/stdc++.h>
using namespace std;

namespace Dinic {
    using i64 = int;
    const i64 Inf = 1e9 + 7;
    struct Dinic {
        int s,t;
        vector<i64> f;
        vector<int> head, cur,ver,Next;
        int tot = 0;
        void add_edge(int x,int y,i64 z) {
            ver[++tot] = y; f[tot] = z; Next[tot] = head[x]; head[x] = tot;
        }
        void add(int x,int y,i64 z) {
            add_edge(x,y,z); add_edge(y,x,0);
        }
        vector<int> dep;
        vector<bool> vis;
        bool bfs() {
            for(int i=1;i<=t;i++) {
                dep[i] = Inf; vis[i] = 0; cur[i] = head[i];
            }
            priority_queue<pair<i64,int> > q;
            q.push({0,s}); dep[s] = 0;
            while(!q.empty()) {
                int x = q.top().second; q.pop();
                if(vis[x]) continue;
                vis[x] = 1;
                for(int i=head[x];i;i=Next[i]) {
                    int y=ver[i]; i64 z = f[i];
                    if(dep[y] > dep[x] + 1 && z) {
                        dep[y] = dep[x] + 1;
                        if(!vis[y]) q.push({-dep[y],y});
                    }
                }
            }
            if(dep[t] != Inf) return 1;
            else return 0;
        }
        bool vst = 0;
        long long dfs(int rt,long long flow) {
            long long limit = 0;
            if(rt == t) {
                vst = 1; return flow;
            }
            for(int i=cur[rt];i;i=Next[i]) {
                cur[rt] = i;
                int y=ver[i];
                long long z = f[i];
                if(z && dep[y] == dep[rt] + 1) {
                    i64 fl = dfs(y,min(flow-limit , z));
                    if(fl) {
                        limit += fl;
                        f[i] -= fl;
                        f[i ^ 1] += fl;
                    }
                }
                if(limit == flow) break;
            }
            return limit;
        }
        long long Run_Dinic() {
            long long flow = 0;
            while(bfs()) {
                long long lowflow;
                vst = 1;
                while(vst) {
                    vst = 0;
                    lowflow = dfs(s,Inf);
                    flow += lowflow;
                }
            }
            return flow;
        }
        void init() {
            tot = 1;
            fill(head.begin() , head.end() , 0);
        }
        Dinic(int _s , int _t ,int head_num , int edges_num) : s(_s) , t(_t) ,
        head(head_num+1) , cur(head_num+1),dep(head_num+1),vis(head_num+1),
        f(edges_num * 2 + 2) , ver(edges_num * 2 + 2) , Next(edges_num*2+2) {
            tot=1;
        }
    };
}
const int N = 2e5;
const int M = 6e5;
Dinic::Dinic s(N * 2 + 1 , N * 2 + 2 , N * 2 + 2 , N * 2 + M);
void solve() {
    int n , m;
    cin>>n>>m;
    s.init();
    s.s = n * 2 + 1 , s.t = n * 2 + 2;
    for(int i=1;i<=n;i++) {
        s.add(n*2 + 1 , i , 1);
        s.add(i+n,n * 2 + 2 , 1);
    }
    for(int i=1;i<=m;i++) {
        int x,y;
        cin>>x>>y;
        y+=n;
        s.add(x , y , 1);
    }
    s.Run_Dinic();

    int L = 0 , R = 0;

    auto bfs = [&](int st,int& ans , int flags) {
        vector<bool> vis(n * 2 + 10);
        queue<int> q; q.push(st); vis[st] = true;
        while(!q.empty()) {
            int x = q.front(); q.pop();
            for(int i=s.head[x];i;i=s.Next[i]) {
                int y=s.ver[i]; int z = s.f[i];
                if(vis[y] || z == flags) continue;
                vis[y] = true;
                q.push(y);
            }
        }
        if(flags)
            for(int i=n+1;i<=n+n;i++) ans += vis[i];
        else
            for(int i=1;i<=n;i++) ans += vis[i];
    };
    bfs(2 * n + 1 , L , 0);
    bfs(2 * n + 2 , R , 1);
    cout<<1ll * L * R<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int T = 1; cin>>T;
    while(T--) solve();
    return 0;
}