#include<bits/stdc++.h>
using namespace std;
constexpr int M=(1<<18)+5;
int n,m,e[18],res[M],cyc[M];
int read(){
	int x=0;char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x;
}
void solve(){
	n=read();m=read();
	for (int i=0;i<n;i++) e[i]=0;
	for (int i=0;i<m;i++){
		int x=read()-1,y=read()-1;
		e[x]|=1<<y;
	} int ans=n;
	for (int sta=0;sta<1<<n;sta++) res[sta]=0;
	for (int i=n-1;i;i--){ cyc[0]=e[i];
		for (int sta=1;sta<1<<i;sta++) cyc[sta]=0;
		for (int sta=0;sta<1<<i;sta++)
			for (int j=0;j<i;j++) if (~sta>>j&1&&cyc[sta]>>j&1)
				cyc[sta^1<<j]|=e[j];
		for (int sta=0;sta<1<<i;sta++)
			if (cyc[sta]>>i&1) res[sta|1<<i]=1;
	}
	for (int sta=1;sta<1<<n;sta++)
		for (int i=0;i<n;i++)
			if (sta>>i&1)
				res[sta]|=res[sta^1<<i];
	for (int sta=0;sta<1<<n;sta++)
		if (!res[sta]) ans=min(ans,n-__builtin_popcount(sta));
	printf("%d\n",ans+n);
}
int main(){int T=read();while (T--) solve(); return 0;}