#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
const int N=19;
int f[1<<N|5];
int g[N],h[1<<N|5];
void solve() {
    int n,m;
    cin >> n >> m;
    FOR(i,0,n-1) g[i]=0;
    FOR(i,1,m) {
        int x,y;
        cin >> x >> y;
        --x,--y;
        g[x]|=1<<y;
    }
    FOR(i,0,(1<<n)-1) f[i]=1e9;
    f[0]=0;
    FOR(i,0,(1<<n)-1) {
        FOR(j,0,n-1) h[1<<j]=1;
        FOR(j,0,n-1) if((1<<j)&i) {
            h[g[j]^(g[j]&i)]++;
        }
        FOR(j,0,n-1) if(!((1<<j)&i)) {
            f[i|(1<<j)]=min(f[i|(1<<j)],h[1<<j]+f[i]);
        }
    }
    cout << f[(1<<n)-1] << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}