#include<bits/stdc++.h>

#define reg register int

#define il inline

#define fi first

#define se second

#define mk(a,b) make_pair(a,b)

#define numb (ch^'0')

#define pb push_back

#define solid const auto &

#define enter cout<<endl

#define pii pair<int,int>

using namespace std;

typedef long long ll;

template<class T>il void rd(T &x){

    char ch;x=;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);(fl==true)&&(x=-x);}

template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}

template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}

template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}

namespace Modulo{

const int mod=;

il int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;}

il int sub(int x,int y){return ad(x,mod-y);}

il int mul(int x,int y){return (ll)x*y%mod;}

il void inc(int &x,int y){x=ad(x,y);}

il void inc2(int &x,int y){x=mul(x,y);}

il int qm(int x,int y=mod-){int ret=;while(y){if(y&) ret=mul(x,ret);x=mul(x,x);y>>=;}return ret;}

template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);}

template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);}

}

using namespace Modulo;

namespace Miracle{

const int N=;

const int M=;

int n,m;

int X[M],Y[M];

int hk[N],lk[N];

int f[N][N];

int c[N][N];

int jie[N],inv[N];

int C(int n,int m){

    if(n<||m<||n<m) return ;

    return c[n][m];

}

int ans,two,one1,one2;

int dp1(int sz){

    int lim=n;

    for(reg i=;i<=n;++i){

        lim-=(hk[i]|lk[i]);

    }

    int ret=;

    for(reg i=;i<=lim;++i){

        inc(ret,mul(C(lim,i),jie[n-sz-i],i&?mod-:));

    }

    return ret;

}

int dp2(int sz){

    int ret=;

    int lim=n;

    for(reg i=;i<=n;++i){

        lim-=(hk[i]|lk[n-i+]);

    }

    for(reg i=;i<=lim;++i){

        inc(ret,mul(C(lim,i),jie[n-sz-i],i&?mod-:));

    }

    return ret;

}

int dp3(int sz){

    memset(f,,sizeof f);

//    cout<<"dp3----------- "<<sz<<endl;

//    prt(hk,1,n);

//    prt(lk,1,n);

    int U,D,L,R;

    int up=(n)/;

    int lim=n-sz;

    if(n&){

        U=D=L=R=(n+)/;

        f[][]=;

        f[][]=(lk[L]==&&hk[U]==);

        --U;--L;++R;++D;

    }else{

        U=L=(n/);D=R=(n/)+;

        f[][]=;

    }

    for(reg i=;i<up;++i){

        int o=min(*i+(n&),lim);

        for(reg j=;j<=o;++j){

            if(f[i][j]){

                int v=f[i][j];

                inc(f[i+][j],v);

//                if(lk[R]+hk[U]==0)inc(f[i+1][j+1],v);

//                if(lk[R]+hk[D]==0)inc(f[i+1][j+1],v);

//                if(lk[L]+hk[U]==0)inc(f[i+1][j+1],v);

//                if(lk[L]+hk[D]==0)

                inc(f[i+][j+],mul((lk[R]+hk[U]==)+(lk[R]+hk[D]==)+(lk[L]+hk[U]==)+(lk[L]+hk[D]==),v));

                if(lk[R]+hk[U]==&&lk[L]+hk[D]==)inc(f[i+][j+],v);

                if(lk[R]+hk[D]==&&lk[L]+hk[U]==)inc(f[i+][j+],v);

            }

        }

        --U;--L;++R;++D;

    }

    int ret=;

    for(reg j=;j<=lim;++j){

        inc(ret,mul(f[up][j],jie[n-sz-j],j&?mod-:));

    }

//    cout<<" ret "<<ret<<endl;

    return ret;

}

int dp4(int sz){

    return jie[n-sz];

}

void clear(){

    memset(f,,sizeof f);

    memset(X,,sizeof X);

    memset(Y,,sizeof Y);

    ans=;

    one1=;one2=;two=;

}

int main(){

    int t;

    rd(t);

    c[][]=;

    n=;

    for(reg i=;i<=n;++i){

        c[i][]=;

        for(reg j=;j<=n;++j){

            c[i][j]=ad(c[i-][j],c[i-][j-]);

        }

    }

    jie[]=;

    for(reg i=;i<=n;++i) jie[i]=mul(jie[i-],i);

    while(t--){

        clear();

        rd(n);rd(m);

        for(reg i=;i<=m;++i){

            rd(X[i]);rd(Y[i]);

            ++X[i];++Y[i];

        }

//        ans=1;

//        for(reg i=1;i<=n;++i) inc2(ans,i);

        ans=;

        for(reg s=;s<(<<m);++s){

            memset(hk,,sizeof hk);

            memset(lk,,sizeof lk);

            int sz=__builtin_popcount(s);

            int c=(sz&)?mod-:;

            bool fl1=true,fl2=true,fl=true;

            for(reg i=;i<=m;++i){

                if((s>>(i-))&){

                    if(X[i]==Y[i]) fl1=false;

                    if(X[i]+Y[i]==n+) fl2=false;

                    if(hk[X[i]]) fl=false;

                    ++hk[X[i]];

                    if(lk[Y[i]]) fl=false;

                    ++lk[Y[i]];

                }

            }

//            cout<<" s "<<s<<" "<<fl1<<" "<<fl2<<" "<<fl<<endl;

            if(fl&&fl1){

                inc(one1,mul(c,dp1(sz)));

            }

            if(fl&&fl2){

                inc(one2,mul(c,dp2(sz)));

            }

            if(fl&&fl1&&fl2){

                inc(two,mul(c,dp3(sz)));

            }

            if(fl){

                inc(ans,mul(c,dp4(sz)));

            }

        }

//        cout<<" one1 "<<one1<<endl;

//        cout<<" one2 "<<one2<<endl;

//        cout<<" two "<<two<<endl;

        inc(ans,ad(mod-one1,mod-one2,two));

//        cout<<ans<<endl;l

        printf("%d\n",ans);

    }

    return ;

}

}

signed main(){

//    freopen("rook.in","r",stdin);

//    freopen("rook.out","w",stdout);

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

*/