I was given the task to make all the major two way roads in Bangladesh into one way roads. And I have done that easily with some great pruning. And I asked the Govt. Traffic Management System to change the direction of all the roads.

But after some days, I realized that I should have thought of the fact that all cities should be reachable from other cities using the existing one way roads. Since the traffic system is already designed, so it may not be changed. But I can ask the govt. to build new roads between any pair of cities.

Now since the task looks quite hard for me, I am asking you to do it for me. I will give you the current roads configuration. You have to find the minimum number of roads that have to be built such that it's possible to go from any city to any other city.

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

Each case starts with a blank line. Next line contains two integers n (1 ≤ n ≤ 20000) and m (0 ≤ m ≤ 50000), where n denotes the number of cities and m denotes the number of one way roads. Each of the next m lines contains two integers u v (1 ≤ u, v ≤ n, u ≠ v) meaning that there is a road from u to v. Assume that there can be at most one road from a city u to v.

For each case, print the case number and the minimum number of roads that have to be built.

Dataset is huge. Use faster I/O methods.