NPLANAR

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF (1<<29)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define REP(i, n) FOR(i, 0, n)
#define F(n) REP(i, n)
#define FF(n) REP(j, n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
#define MX 3333
struct tr{int a,b,c;}T[256];
#define SQ (47)
struct bs{
    ll A[SQ];
    void clr(){CL(A,0);}
    void operator&=(bs&r){F(SQ)A[i]&=r.A[i];}
    void ad(int u){A[u>>6]|=1ull<<(u&63);}
    bool ct(int v){return (A[v>>6]>>(v&63))&1;}
    int xt(int u){
        while(++u&63)if((A[u>>6]>>(u&63))&1)return u;
        while(u<SQ<<6&&!A[u>>6])++u;
        if(u==SQ<<6)return -1;
        while(!ct(u))++u;
        return u;
    }
}B[MX],t;
vi g[MX];
int fcl(int N){
    int L(0),a;
    F(N)B[i].clr();
    F(N)for(auto&h:g[i])B[i].ad(h);
    F(N)for(auto&h:g[i])if(i<h){
        t=B[i],t&=B[h],a=h;
        while(~(a=t.xt(a)))T[L++]={i,h,a};
    }
    return L;
}
int N,M,a,b,L,cn[MX];
bool con(tr&a,tr&b){return a.a==b.a||a.a==b.b||a.a==b.c||a.b==b.a||a.b==b.b||a.b==b.c||a.c==b.a||a.c==b.b||a.c==b.c;}
unordered_map<ll,int> dp;
int dyn(int u,ll b){
    if(dp.count(b))return dp[b];
    while(b&1ull<<u)++u;
    if(u==L)return 0;
    int S(INF);
    for(auto&h:g[u])if(!(1ull<<h&b))S=min(S,1+dyn(u+1,b|1ull<<h|1ull<<u));
    if(S==INF)S=dyn(u+1,b|1ull<<u)+1;
    return dp[b]=S;
}
int main(void){
    IN(tt)F(tt){
        CL(cn,-1),L=0,dp.clear();for(auto&h:g)h.clear();
        scanf("%d%d",&N,&M);
        F(M)scanf("%d%d",&a,&b),g[--a].PB(--b),g[b].PB(a);
        L=fcl(N);for(auto&h:g)h.clear();
        F(L)FT(i+1,L)if(con(T[i],T[k]))g[i].PB(k);
        printf("%d\n",dyn(0,0));
    }
    return 0;
}