# Friends

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

There are $n$ people and $m$ pairs of friends. For every pair of friends, they can choose to become online friends (communicating using online applications) or offline friends (mostly using face-to-face communication). However, everyone in these $n$ people wants to have the same number of online and offline friends (i.e. If one person has $x$ onine friends, he or she must have $x$ offline friends too, but different people can have different number of online or offline friends). Please determine how many ways there are to satisfy their requirements.

## Input

The first line of the input is a single integer $T\ (T=100)$, indicating the number of testcases.

For each testcase, the first line contains two integers $n\ (1 \le n \le 8)$ and $m\ (0 \le m \le \frac{n(n-1)}{2})$, indicating the number of people and the number of pairs of friends, respectively. Each of the next $m$ lines contains two numbers $x$ and $y$, which mean $x$ and $y$ are friends. It is guaranteed that $x \neq y$ and every friend relationship will appear at most once.

## Output

For each testcase, print one number indicating the answer.

## Sample Input

2
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1

## Sample Output

0
2

wange2014

## Source

2015 Multi-University Training Contest 2