#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<string.h>
#include <string>
#include<math.h>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<queue>
#include<stack>
#include<functional>
#include<deque>
using namespace std;

const int MAXN = 201000;
#define int long long
#define ll long long
#define lll unsigned long long
#define PA pair<ll,ll>
#define INF (ll)0x3f3f3f3f*(ll)1000000
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const ll mod = 1e9 + 7;



void solve() {
	int n, m; cin >> n >> m;
	vector<vector<int>>left(n + 1);
	for (int i = 1; i <= m; i++) {
		int x, y; cin >> x >> y;
		left[x].push_back(y);
	}

	bool visit[MAXN];
	vector<int>match(n + 1, 0);

	function<bool(int)>check = [&](int x)->bool {
		for (auto y : left[x]) {
			if (!visit[y]) {
				visit[y] = true;
				int t = match[y];
				if (!t || check(t)) {
					match[y] = x;
					return true;
				}
			}
		}
		return false;
	};

	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		memset(visit, 0, sizeof visit);
		if (check(i)) {
			cnt++;
		}
	}
	
	int s = 0, t = 2 * n + 1;
	vector<vector<int>>edge(2 * n + 2);

	vector<bool>canusel(n + 1, true);
	vector<bool>canuser(n + 1, true);
	for (int i = 1; i <= n; i++) {
		if (match[i]) {
			canusel[match[i]] = false;
			canuser[i] = false;
		}
	}

	for (int i = 1; i <= n; i++) {
		if (canusel[i]) {
			edge[i].push_back(s);
			edge[s].push_back(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (canuser[i]) {
			edge[i + n].push_back(t);
			edge[t].push_back(i + n);
		}
	}

	for (int i = 1; i <= n; i++) {
		for (auto y : left[i]) {
			edge[i].push_back(y + n);
			edge[y + n].push_back(i);
		}
	}

	vector<bool>visl(2 * n + 2, false);
	function<int(int, int)>dfsl = [&](int x, int fa)->int {
		int res = 0;
		
		visl[x] = true;
		if (x <= n && x > 0) {
			res++;
		}

		for (auto v : edge[x]) {
			if (v == fa || visl[v])continue;
			res += dfsl(v, x);
		}

		return res;
	};

	vector<bool>visr(2 * n + 2, false);
	function<int(int, int)>dfsr = [&](int x, int fa)->int {
		int res = 0;

		visr[x] = true;
		if (x > n && x <= 2*n) {
			res++;
		}

		for (auto v : edge[x]) {
			if (v == fa || visr[v])continue;
			res += dfsr(v, x);
		}

		return res;
	};

	int resl = dfsl(s, -1);
	int resr = dfsr(t, -1);

	cout << resl * resr << endl;
}

signed main() {
	IOS;
	int t = 1; cin >> t;
	while (t--) {
		solve();
	}
}