### Friends

Time Limit: 1000 ms Memory Limit: 65536 KiB

#### Problem 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 (1n8) and m (0mn(n1)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 xy 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


#### Source

2015 Multi-University Training Contest 2