#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

ll c[][],tmp[];

int main()

{

    int T,m,u,v;

    ll t,ans;

    scanf("%d",&T);

    while(T--)

    {

        memset(c,,sizeof c);

        scanf("%d%d",&n,&m);

        while(m--)

        {

            scanf("%d%d",&u,&v);

            u--;v--;

            c[u][v]--;c[v][u]--;

            c[u][u]++;c[v][v]++;

        }

        ans=;

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

        {

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

            while(c[j][i])

            {

                t=c[i][i]/c[j][i];

                for(int k=i;k<n;++k) c[i][k]-=c[j][k]*t;

                for(int k=i;k<n;++k) swap(c[i][k],c[j][k]);

                ans=-ans;

            }

            ans*=c[i][i];

            if(!ans) break;

        }

        ans=max(ans,-ans);

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

    }

}