IE5 - Hamiltonian Cycles

You are given a complete undirected graph with n nodes numbered from 1 to n. You are also given k forbidden edges in this graph.

You are asked to find the number of Hamiltonian cycles in this graph that don't use any of the given k edges. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A cycle that contains the same edges is only counted once. For example, cycles 1 2 3 4 1 and 1 4 3 2 1 and 2 3 4 1 2 are all the same, but 1 3 2 4 1 is different.

Input

The first line of input gives the number of cases, N (≤ 10). N test cases follow. The first line of each test case contains two integers, n (≤ 300) and k (≤ 15). The next k lines contain two integers each, representing the vertices of a forbidden edge. There will be no self-edges and no repeated edges.

Output

For each test case, output one line containing "Case #X: Y", where X is the case number (starting from 1) and Y is the number of Hamiltonian cycles that do not include any of those k edges. Print your answer modulo 9901.

Example

Input:
2
4 1
1 2
8 4
1 2
2 3
4 5
5 6
Output: Case #1: 1
Case #2: 660

Added by:acheron
Date:2014-02-09
Time limit:1.416s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:GCJ Practice Round

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.