import java.util.Scanner;

public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int case_num = sc.nextInt();
int [] result = new int[case_num];

for(int p=0;p<case_num;p++){
        String line1 = sc.next(); // 사람수, 친구경우수
        line1 = line1 + sc.nextLine();
        String line2 = sc.next(); // 친구조합
        line2 = line2 + sc.nextLine();
        int person_num = Integer.parseInt(line1.split(" ")[0]);
        boolean areFriends[][] = new boolean[person_num][person_num];
        boolean taken[] = new boolean[person_num];

        int temp_x = 0;
        int temp_y = 0; 
        for(int i =0; i<line2.split(" ").length; i=i+2){

            if(Integer.parseInt(line2.split(" ")[i])<Integer.parseInt(line2.split(" ")[i+1])){
                temp_x = Integer.parseInt(line2.split(" ")[i]);
                temp_y = Integer.parseInt(line2.split(" ")[i+1]);

            }else{
                temp_y = Integer.parseInt(line2.split(" ")[i]);
                temp_x = Integer.parseInt(line2.split(" ")[i+1]);

            }
            areFriends[temp_x][temp_y] = true;
        }

        result[p] = findCaseNum(areFriends, taken);

    }

    for(int p=0;p<case_num;p++){
        System.out.println(result[p]);
    }
}       
public static int findCaseNum(boolean[][] areFriends, boolean[] taken){
    int freeFirst = -1;
    // 아직 짝이 없는 사람중에서 가장 낮은 수를 구한다
    for(int i=0;i<taken.length;i++){
        if(!taken[i]){
            freeFirst = i;
            break;
        }
    }
    // taken되지 않은 사람이 없는 경우 하나의 케이스가 완성되므로 return 1;
    if(freeFirst == -1){
        return 1;
    }
    int result = 0;
    // freeFirst와 친구인 사람을 낮은 수부터 찾아서 표시한다.
    for(int withPair = freeFirst+1; withPair < areFriends.length; withPair++){
        if(!taken[withPair]&&areFriends[freeFirst][withPair]){
            taken[freeFirst] = true;
            taken[withPair] = true;
            result = result + findCaseNum(areFriends, taken);


            taken[freeFirst] = false;
            taken[withPair] = false;

        }
    }
    return result;
}

}

** https://algospot.com/judge/problem/read/PICNIC
** 책의 내용대로 java로 재구현 보았는데 런타임 오류가 났습니다.
** RTE 원인을 어떻게 찾아야할지 모르겠습니다.. 제 로컬에서는 잘 돌아가는데 여기에 제출하면 런타임 오류가 나는 이유는 뭘까요 ㅜㅜ
** 원인을 어떻게 찾는지 아시는 분의 도움을 부탁드립니다.