Ants made a large underground network for their communication, consisting of n junctions, and junctions are connected by m underground tunnels. As there are animals/insects that can attack them outside the ground, they made the full network under the ground such that it becomes a safe hideout for them.

The junctions and tunnels are strong but if there is any kind of natural disasters like earthquakes or tornadoes, there is a chance that a junction may collapse. That's why they want to built some escape shafts in junctions (at most one shaft in one junction) that lead them to the surface. Now they want to build minimum number of shafts such that if any of the junctions (only one) collapses, ants that survive the collapse, still have a path to the surface. Now your task is to find the minimum number of shafts, and the number of ways the minimum shafts can be built.

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

Each case starts with a blank line. The next line contains two integers: n (2 ≤ n ≤ 10000) and m (0 ≤ m ≤ 20000). Each of the next m lines contains two integers u v (0 ≤ u, v < n, u ≠ v) meaning that there is a bidirectional tunnel between junction u and v. The input follows the above constraints. And no tunnel is reported more than once. All junctions are connected.

For each case, print the case number, the minimum number of escape shafts and the number of ways they can build the minimum shafts modulo 2⁶⁴.

Dataset is huge, use faster I/O methods.