You are given a simple graph with vertices and edges. A simple graph is an undirected graph that has no self-loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices. Initially, each edge is colored white. Each round you can pick a white edge and paint it in red. You are not allowed to generate an odd-length cycle that consists only of red edges. What's the maximum number of edges that can be painted to red?

输入描述:

The first line of the input gives the number of test case,  ().  test cases follow.
For each case, the first line contains only two integers  and  (, ). 
The i-th line of the next  lines describes the i-th edge: two integers ,  denotes an edge between  and . It's guaranteed that there are no self-loops and multiple edges.

输出描述:

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the maximum number of edges that can be painted to red.

2
4 5
1 2
1 3
1 4
2 4
3 4
5 6
1 2
2 3
3 1
1 4
4 5
3 5

Case #1: 4
Case #2: 5