#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

const int N=,M=9e5+,mod=1e9+;

int n,m,hd[N],xnt,to[M],nxt[M],b[N][N],f[N][N];

bool vis[N];

void init()

{

  memset(b,,sizeof b); memset(f,,sizeof f);

  xnt=; memset(hd,,sizeof hd);

}

void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}

void dfs(int cr)

{

  for(int i=hd[cr],v;i;i=nxt[i])

    if(!vis[v=to[i]])

      {

    vis[v]=; b[cr][v]=; dfs(v);

      }

}

bool chk(int x1,int x2,int y1,int y2)

{

  if(x2<x1||y2<y1)return true;

  int tp=b[x2][y2]-b[x1-][y2]-b[x2][y1-]+b[x1-][y1-];

  return !tp;

}

void solve()

{

  for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

      b[i][j]+=b[i][j-];

  for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

      b[i][j]+=b[i-][j];

  for(int len=;len<=n;len++)

    {

      for(int i=;i<=n;i++)

    {

      int j=i+len-; if(j>n)break;

      f[i][i-]=f[j+][j]=;

      for(int k=i;k<=j;k++)

        {

          if(chk(k,j,i,k-)&&chk(k,k,k+,j))

        f[i][j]=(f[i][j]+(ll)f[i][k-]*f[k+][j])%mod;

        }

    }

    }

  printf("%d\n",f[][n]);

}

int main()

{

  int T=rdn();

  while(T--)

    {

      init();

      n=rdn();m=rdn();

      for(int i=,u,v;i<=m;i++)

    u=rdn(),v=rdn(),add(u,v);

      for(int i=;i<=n;i++)

    {

      memset(vis,,sizeof vis);

      dfs(i);

    }

      bool fg=;

      for(int i=;i<=n&&(!fg);i++)

    for(int j=;j<=i;j++)

      if(b[i][j]&&b[j][i]){fg=;break;}

      if(fg){puts("");continue;}

      solve();

    }

  return ;

}