#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define pii pair<int, int>
const ll inf = 1145141919810;
using namespace std;
struct Dinic {
	ll st, ed, n, m, cnt;
	vector<ll> nxt{0, 0}, to{0, 0}, c{0, 0}, head, pre, cur, d;

	Dinic(int _n, int _st, int _ed){
		n = _n, st = _st, ed = _ed, cnt = 1;
		head.resize(n + 10), pre.resize(n + 10), cur.resize(n + 10), d.resize(n + 10);
	}
    
    void Add(int x, int y, ll z) { nxt.push_back(head[x]), to.push_back(y), c.push_back(z), head[x] = ++cnt;};
	void add(int x, int y, ll z) { Add(x, y, z), Add(y, x, 0);}
	bool bfs() {
		for(int i = 1; i <= n; ++i) d[i] = 0;
		queue<ll> q;
		q.push(st), d[st] = 1;
		while(q.size()) {
			int x = q.front();
			q.pop();
			for(int i = head[x]; i; i = nxt[i])
				if(d[to[i]] == 0 && c[i]) {
					d[to[i]] = d[x] + 1;
					q.push(to[i]);
					if(to[i] == ed) return 1;
				}
		}
		return 0;
	}
	ll dfs(int x, ll mf) {
		if(x == ed) return mf;
		ll sum = 0;
		for(int i = cur[x]; i; i = nxt[i]) {
			cur[x] = i;
			if(d[to[i]] == d[x] + 1 && c[i]) {
				ll f = dfs(to[i], min(c[i], mf));
				c[i] -= f, c[i ^ 1] += f;
				sum += f, mf -= f;
				if(mf == 0) break;
			}
		}
		if(sum == 0) d[x] = 0;//剪枝
		return sum;//这个就是这个点的ans
	}
	ll dinic() {
		ll flow = 0;
		while(bfs()) cur = head, flow += dfs(st, inf);
		return flow;
	}
};
void slv(){
    int n, m;
    cin >> n >> m;
    Dinic d(2 * n, 2 * n + 1, 2 * n + 2);
	vector<int> v1, v2, v(2 * n + 5);
	queue<int> st, ed;

	for(int i = 1; i <= n; ++i) d.add(d.st, i, 1);
	for(int i = 1; i <= n; ++i) d.add(i + n, d.ed, 1);

	while(m--){
		int x, y;
		cin >> x >> y;
		d.add(x, y + n, 1);
	}

	d.dinic();
	st.push(d.st), ed.push(d.ed);

	while(st.size()){
		int x = st.front(); st.pop();
		v[x] = 1;
		if(x != d.st && x <= n) v1.push_back(x);
		for(int i = d.head[x]; i; i = d.nxt[i]){
			if(d.c[i] && !v[d.to[i]]) st.push(d.to[i]);
		}
	}
	while(ed.size()){
		int x = ed.front(); ed.pop();
		v[x] = 1;
		if(x != d.ed && x > n) v2.push_back(x);
		for(int i = d.head[x]; i; i = d.nxt[i]){
			if(d.c[i ^ 1] && !v[d.to[i]]) ed.push(d.to[i]);
		}
	}

	cout << (ll)v1.size() * v2.size() << endl;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int _ = 1;
    cin >> _;
    while(_--) slv();
    return 0;
}