Mr. Xu is a student of CSE who is very curious in graph theory. In past years he solved different types of graph problems, now he faced a problem with graph theory please help Mr. Xu to solve this problem.

Mr. Xu defined his problem like this:

Give a graph with N vertices and E edges where N denotes the number of vertices and E denotes the number of bi-directional edges. This graph may contain one or more cycles, in graph theory a cycle means closed walk, consisting of a sequence of vertices starting and ending at the same vertex, with every two consecutive vertices in the sequence adjacent to each other in the graph.

Now if a vertex is part of only one simple cycle then we called this vertex is a Good vertex.

A simple cycle is a closed walk with no repetition of vertices or edges allowed, other than the repetition of the starting and ending vertex.

If a simple cycle contains more than two vertexes and all vertices are Good vertexes then we define this cycle as a Golden cycle.

Now he tries to find how many Golden cycles are containing in the given graph.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each test case contains two integers N (1 ≤ N ≤ 20000), E (1 ≤ E ≤ 50000).N denotes the number of vertices and E denotes the number of bi-directional edges. Each of the next E lines will contain two different integers u v (1 ≤ u, v ≤ n) denoting that there is an edge between u and v.

Output

For each case, print the case number and the total number of Golden cycles.