#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void set_friends (int [][10], int, int);
int count_parings(int [][10], int [], int);

int main() {

    int i=0, j=0;
    int n=0, m=0;   //n은 학생 수, m 은 짝의 수 입니다.
    int test_case=0;
    int result=0;
    int taken[10] = {0,};
    int are_friends[10][10] = {0,};

    scanf ("%d", &test_case);
    if ( test_case<0 || test_case >50) {
        printf ("Error: 0<Testcase<= 50\n");
        exit(0);
    }

    while ( test_case>0) {

        // initialization.
        for (i=0 ; i<10 ; i++) {
            taken[i] = 0;
            for (j=0 ; j<10 ; j++) {
                are_friends[i][j] = 0;
            }
        }

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

        // check boudary of n
        if (n<2 || n>10) {
            printf ("Error: 2<=N<=10\n");
            exit(1);
        }
        else if (n%2) {
            printf ("Error : The number of student must be even number.\n");
            exit(1);
        }
        // check boundary of m
        if ( m<0 || m>(n*(n-1))/2 ) {
            printf ("Error: 0<=M<=n(n-1)/2\n");
            exit(1);
        }

        set_friends(are_friends, n, m);

        result = count_parings(are_friends, taken, n);

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


        test_case--;
    }

    return 0;
}

// 짝을 입력받는 함수입니다.
void set_friends (int are_friends[][10], int n, int m) {

    int count=0;
    int coordinate=0, x=0, y=0;
    char *token=NULL;
    char temp[30]={0,};


    gets(temp);

    token = strtok(temp," ");

    x = y = -1;
    while (token) {
        coordinate = atoi(token);

        if ( coordinate<0 || coordinate>=n) {
            printf ("Error: 0 <= Stundent number <= n-1\n");
            exit(1);
        }

        if (x==-1) {
            x = coordinate;
        }
        else if (y==-1) {
            y = coordinate;
        }

        if (x!=-1 && y!=-1) {
            are_friends[x][y] = 1;
            are_friends[y][x] = 1;

            x=-1;
            y=-1;
        }

        token = strtok(NULL, " ");
        count++;
    }
 }

int count_parings(int are_friends[][10], int taken[], int n) {

    int ret=0, pair_with=0;
    int first_free = -1;

    for (int i=0 ; i<n ; i++) {
        if (!taken[i]) {
            first_free = i;
            break;
        }
    }

    if (first_free == -1) {
        return 1;
    }

    for (pair_with = first_free+1 ; pair_with<n ; pair_with++) {

        if ( !taken[pair_with] && are_friends[first_free][pair_with] ) {
            taken[first_free] = taken[pair_with] = 1;
            ret += count_parings(are_friends, taken, n);
            taken[first_free] = taken[pair_with] = 0;
        }

    }

    return ret;


}