#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
vector<int> g[17];
int am[17][17];
int u[17];
int f=0;
void dfs(int x, int c){
if (f) return;
if (u[x]>2) return;
if (u[x]==0){
u[x]=c;
}
else{
if (u[x]!=c){
f=1;
}
return;
}
for (int nx:g[x]){
dfs(nx, 3-c);
}
}
int isbp(int n){
f=0;
for (int i=1;i<=n;i++){
if (u[i]==0){
dfs(i, 1);
if (f) return 0;
}
}
return 1;
}
void solve(){
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++) g[i].clear();
for (int i=1;i<=n;i++){
for (int ii=1;ii<=n;ii++) am[i][ii]=0;
}
for (int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a++;
b++;
g[a].push_back(b);
g[b].push_back(a);
am[a][b]=1;
am[b][a]=1;
}
if (m==0){
cout<<1<<'\n';
return;
}
for (int i=1;i<=n;i++) u[i]=0;
if (isbp(n)){
cout<<2<<'\n';
return;
}
for (int b=1;b<(1<<n);b++){
for (int i=0;i<n;i++){
if (b&(1<<i)){
u[i+1]=3;
}
else{
u[i+1]=0;
}
}
int ff=0;
for (int i=1;i<=n;i++){
if (u[i]==0) continue;
for (int ii=i+1;ii<=n;ii++){
if (u[i]==u[ii]&&am[i][ii]){
ff=1;
break;
}
}
}
if (ff) continue;
if (isbp(n)){
cout<<"3\n";
return;
}
}
for (int b=1;b<(1<<n);b++){
for (int i=0;i<n;i++){
if (b&(1<<i)){
u[i+1]=3;
}
else{
u[i+1]=0;
}
}
if (!isbp(n)) continue;
for (int i=0;i<n;i++){
if (b&(1<<i)){
u[i+1]=0;
}
else{
u[i+1]=3;
}
}
if (!isbp(n)) continue;
cout<<"4\n";
return;
}
cout<<"many"<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int tcs;
cin>>tcs;
for (int tc=0;tc<tcs;tc++){
solve();
}
}