#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, to, head, c, pre, cur, d;
	Dinic(int _n, int _m, int _st, int _ed){//点数，边数，原点，会点。
		n = _n, m = _m, st = _st, ed = _ed, cnt = 1;
		nxt.resize(2 * m + 10), to.resize(2 * m + 10), c.resize(2 * m + 10);
		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[++cnt] = head[x], to[cnt] = y, c[cnt] = 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]) {
				int y = to[i];
				if(d[y] == 0 && c[i]) {
					d[y] = d[x] + 1;
					q.push(y);
					if(y == ed) return 1;
				}
			}
		}
		return 0;
	}
	ll dfs(int x, ll mf) { // mf表示剩余的流量
		if(x == ed) return mf;
		ll sum = 0;
		for(int i = cur[x]; i; i = nxt[i]) {
			cur[x] = i;
			int y = to[i];
			if(d[y] == d[x] + 1 && c[i]) {
				ll f = dfs(y, 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, 3 * n + 1, 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);

	for(int i = 0; i < m; ++i){
		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 << v1.size() * v2.size() << endl;
}

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