#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)      for(int i=0;i<(int)(n);++i)
#define FOR(i,a,b)    for(int i=(int)(a);i<=(int)(b);++i)
#define FORD(i,b,a)   for(int i=(int)(b);i>=(int)(a);--i)
#define CLR(x,y)      memset((x),(y),sizeof((x)))
#define parity(x)     __builtin_parity((x))
typedef long long LL;
const int N=45;
int nl,nr;
LL e[N],A[2][1<<20],B[2][1<<20];
void dfs1(int k,int msk,int rc,int ic){
  if(k==nl){
    ++A[ic][rc];
    return;
  }
  dfs1(k+1,msk,rc,ic);
  dfs1(k+1,msk|1<<k,rc^(e[k]>>nl),ic^parity(e[k]&msk));
}
void dfs2(int k,int msk,int ic){
  if(k==nr){
    ++B[ic][msk];
    return;
  }
  dfs2(k+1,msk,ic);
  dfs2(k+1,msk|1<<k,ic^parity((e[k+nl]>>nl)&msk));
}
int main(){
  int T;scanf("%d",&T);
  FOR(cs,1,T){
    int n,m;scanf("%d%d",&n,&m);
    CLR(e,0);
    rep(i,m){
      int u,v;scanf("%d%d",&u,&v);--u,--v;
      e[u]|=1LL<<v,e[v]|=1LL<<u;
    }
    nr=min(n,18),nl=n-nr;
    rep(i,2)rep(j,1<<nr)A[i][j]=B[i][j]=0;    
    dfs1(0,0,0,0);
    dfs2(0,0,0);    
    LL res=0;
    rep(c,2){
      auto &a=A[c],&b=B[c];
      rep(i,nr)
      FORD(j,(1<<nr)-1,0)if(j>>i&1)
        a[j^(1<<i)]+=a[j],b[j^(1<<i)]+=b[j];
    }
    rep(lc,2)
    rep(rc,2){
      static LL c[1<<20];
      auto &a=A[lc],&b=B[rc];
      rep(i,1<<nr)c[i]=a[i]*b[i];      
      rep(i,nr)
      rep(j,1<<nr)if(j>>i&1)
        c[j^(1<<i)]-=c[j];      
      rep(i,1<<nr)if(parity(i)^lc^rc)
        res+=c[i];            
    }
    printf("Case #%d: %lld\n",cs,res);
  }
  return 0;
}