// Arup Guha
// 7/31/2013
// Solution to 2011 UCF Locals Problems Gold and Black Cactus

import java.util.*;

public class cactus {

	public final static int MOD = 1007;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Go through each case.
		for (int loop=1; loop<=numCases; loop++) {

			// Read in the graph.
			int n = stdin.nextInt();
			int e = stdin.nextInt();
			ArrayList[] graph = new ArrayList[n];
			for (int i=0; i<n; i++)
				graph[i] = new ArrayList<Integer>();
			for (int i=0; i<e; i++) {
				int v1 = stdin.nextInt()-1;
				int v2 = stdin.nextInt()-1;
				graph[v1].add(v2);
				graph[v2].add(v1);
			}

			// Get rid of edges not in cycles.
			trim(graph);

			// Now, solve the problem with the reduced graph.
			System.out.println("Case #"+loop+": "+solve(graph));
			System.out.println();
		}
	}

	// Iteratively gets rid of all vertices with degree one, and their associated edges.
	public static void trim(ArrayList[] graph) {

		// Outer loop - we'll kick out when there are no vertices of degree 1.
		while (true) {

			boolean flag = false;
			for (int i=0; i<graph.length; i++) {
				if (graph[i].size() == 1) {
					int item = (Integer)graph[i].get(0);
					graph[i] = new ArrayList<Integer>();
					graph[item].remove(new Integer(i));
					flag = true;
				}
			}

			if (!flag) break;
		}
	}

	public static int solve(ArrayList[] graph) {

		int count = 1;
		int n = graph.length;

		// Keeps track of visited vertices.
		boolean[] visited = new boolean[n];
		for (int i=0; i<n; i++)
			if (graph[i].size() == 0)
				visited[i] = true;

		// Will keep track of unvisited edges.
		ArrayList[] edgeVisited = new ArrayList[n];
		for (int i=0; i<n; i++) {
			edgeVisited[i] = new ArrayList<Boolean>();
			for (int j=0; j<graph[i].size(); j++)
				edgeVisited[i].add(false);
		}

		// Go through each edge in the graph.
		for (int i=0; i<n; i++) {
			for (int j=0; j<edgeVisited[i].size(); j++) {

				// Next edge to use in our search.
				if (!((Boolean)edgeVisited[i].get(j))) {

					// Initialize our search from this edge.
					Stack<edge> s = new Stack<edge>();

					// Set both copies of this edge to visited, as well as the vertices.
					edgeVisited[i].set(j, true);
					int next = (Integer)graph[i].get(j);
					setTrue(edgeVisited, graph, next, i);
					visited[i] = true;
					visited[next] = true;
					s.push(new edge(i,next));

					// Run till we've popped off all cycles.
					while ( s.size() > 0 ) {

						int cur = s.peek().v2;
						boolean mainFlag = false;

						// Look to add an edge to our stack.
						for (int k=0; k<edgeVisited[cur].size(); k++) {
							if (!((Boolean)edgeVisited[cur].get(k))) {
								mainFlag = true;
								next = (Integer)graph[cur].get(k);
								edgeVisited[cur].set(k, true);
								setTrue(edgeVisited, graph, next, cur);

								// Found a cycle!
								if (visited[next]) {

									// Pop off items until we get to the start of the cycle.
									int cycleSize = 1;
									while (s.size() > 0 && s.peek().v1 != next) {
										cycleSize++;
										edge tmp = s.pop();
									}
									if (s.size() > 0) {
										s.pop();
										cycleSize++;
									}

									// Add this into our count.
									count = (count*cycleSize)%MOD;
								}

								// Add to stack.
								else {
									visited[next] = true;
									s.push(new edge(cur, next));
								}

								// Need to get out, since we processed an edge from here.
								break;
							}
						}

						// Without this, on some graphs, we never end.
						if (!mainFlag) break;
					}
				}
			}
		}

		return count;
	}

	// Sets the edge start to end to true.
	public static void setTrue(ArrayList[] edgeVisited, ArrayList[] graph, int start, int end) {
		for (int k=0; k<graph[start].size(); k++) {
			if ((Integer)graph[start].get(k) == end) {
				edgeVisited[start].set(k, true);
				return;
			}
		}
	}
}

class edge {

	public int v1;
	public int v2;

	public edge(int a, int b) {
		v1 = a;
		v2 = b;
	}
}