A group of N people are going to the movies, some pair of them are friends and according to the famous saying that "The friends of my friends are my friends, too" it follows that if A and B are friends and B and C are friends then A and C are friends, and do not forget that every friendship is mutual, if A is friend of B, then B is also friend of A. They will all sit in the first row at the cinema, there are N seats in each row, a way is good if there is at least one pair of people that are friends and at the same time they are sitting in adjacent seats. So that is your task, to count how many assignments of those N people in the N seats are good.

Input

Input starts with an integer T (1 <= T <= 600), denoting the number of test cases. Each test case starts with a line containing two integers N (2 <= N <= 40) and M (0 <= M <= 800). Each of the next M lines will contain 2 integers A B (1 <= A,B <= N, A != B) meaning that A and B are friends.

Output

For each test case print a single line with "Case #X: P" where X is the number of the test case (starting from 1) and P is the number of ways modulo 1000000007. Look at the sample output for more details.

Example

Input:
3
2 1
2 1
3 2
2 1
1 3
4 0

Output:
Case #1: 2
Case #2: 6
Case #3: 0