#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];
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;
    }
    f[0]=0;
    FOR(i,1,(1<<n)-1) {
        f[i]=1e9;
        FOR(j,0,n-1) if((1<<j)&i) {
            int c=1;
            FOR(k,0,n-1) if(k!=j && ((1<<k)&i) && (g[k]&i)==g[k] && (g[k]&(i^(1<<j)))!=g[k]) {
                ++c;
            }
            // if(i==7) cerr << j << ' ' << ' ' << f[i^(1<<j)] << ' ' << c << endl;
            f[i]=min(f[i],f[i^(1<<j)]+c);
        }
        // cerr << i << " = " << f[i] << endl;
    }
    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;
}