#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
const ll N = 50;
const ll M = 2e3;
inline ll read() {ll x; return scanf("%lld", &x), x;}
ll n, m;
ll bit[2][N + 5];
#define lowbit __builtin_ctzll
inline bool check(ll type)
{
	static ll s, q[N + 5], l, r;
	s = (1ll << n) - 1, l = 1, r = 0;
	q[ ++ r] = 0;
	while (l <= r)
	{
		ll u = q[l ++ ], t = bit[type][u] & s;
		while (t)
		{
			ll v = q[ ++ r] = lowbit(t);
			s ^= 1ll << v, t ^= 1ll << v;
		}
	}
	return !s;
}
inline bool lets_check_check() {return check(0) && check(1);}
ll bang[N + 5];
ll f[N + 5], g[N + 5];
ll dfn[N + 5], low[N + 5], tim;
ll stack[N + 5], top;
bool in_stack[N + 5];
ll scc;
void tarjan(ll u)
{
	dfn[u] = low[u] = ++ tim;
	stack[ ++ top] = u;
	in_stack[u] = 1;
	for (ll v = 0; v < n; v ++ )
	{
		if (bit[0][u] >> v & 1 ^ 1) continue; 
		if (!dfn[v]) tarjan(v), low[u] = std :: min(low[u], low[v]), f[v] = u;
		else if (in_stack[v]) if (low[u] > dfn[v]) low[u] = dfn[v], g[u] = v;
	}
	if (dfn[u] == low[u])
	{
		scc ++ ;
		do in_stack[stack[top]] = 0; while (stack[top -- ] != u) ;
	}
}
ll res;
void dfs(ll dep)
{
	if (dep == 3) return res -= lets_check_check(), void();
	ll ip[N + 5];
	std :: memset(ip, 0, sizeof ip);
	std :: memset(f, -1, sizeof f), std :: memset(g, -1, sizeof g);
	scc = tim = 0;
	std :: memset(dfn, 0, sizeof dfn);
	for (ll i = 0; i < n; i ++ ) if (!dfn[i]) tarjan(i);
	if (scc > 1) return ;
	for (ll i = 0; i < n; i ++ )
	{
		if (~f[i]) ip[f[i]] |= 1ll << i;
		if (~g[i]) ip[i] |= 1ll << g[i];
	}
	ll cnt = 0;
	for (ll i = 0; i < n; i ++ )
		for (ll j = 0; j < n; j ++ )
		{
			if (bit[0][i] >> j & 1 ^ 1) continue;
			if (bang[i] >> j & 1) {if (ip[i] >> j & 1) ip[i] ^= 1ll << j; continue;}
			if (ip[i] >> j & 1) continue;
			cnt ++ ;
		}
	if (dep == 0) res -= (ll)cnt * (cnt - 1) * (cnt - 2) / 6;
	if (dep == 1) res -= cnt * (cnt - 1) / 2;
	if (dep == 2) res -= cnt;
	for (ll i = 0; i < n; i ++ )
	{
		for (ll j = 0; j < n; j ++ )
		{
			if (ip[i] >> j & 1 ^ 1) continue;
			bit[0][i] ^= 1ll << j, bit[1][j] ^= 1ll << i;
			dfs(dep + 1);
			bit[0][i] ^= 1ll << j, bit[1][j] ^= 1ll << i;
			bang[i] ^= 1ll << j;
		}
	}
	for (ll i = 0; i < n; i ++ )
	{
		for (ll j = 0; j < n; j ++ )
		{
			if (ip[i] >> j & 1 ^ 1) continue;
			bang[i] ^= 1ll << j;
		}
	}
}
int main()
{
	ll T = read();
	while (T -- )
	{
		n = read(), m = read();
		std :: memset(bit, 0, sizeof bit);
		res = (ll)m * (m - 1) * (m - 2) / 6;
		while (m -- )
		{
			ll u = read() - 1, v = read() - 1;
			bit[0][u] |= 1ll << v, bit[1][v] |= 1ll << u;
		}
		dfs(0);
		printf("%lld\n", res);
	}
	return 0;
}