Hanzo Hattori rescued Princess Nakururu and now they are planning to escape from the castle, because it's going to explode. Now the problem is that Nakururu is not quite well that's why she can't run all the way. And Hattori is also injured. That's why he can't carry her all the way.

So, they made a plan. From their current position, Hanzo will carry Nakururu to the next place. Then they both will run to the next place. Then again Hanzo will carry Nakururu to the next place. And they will continue this procedure to go from one place to another.

Each place can be treated as a node. Nodes are connected by bi-directional roads. All the nodes are numbered as integers. Initially they are at node 1. And both of them will run to the next node.

Now given the description of the nodes and roads you have to count the number of possible nodes which can be entered by Hanzo carrying Nakururu with him. Initially Hattori doesn't carry Nakururu.

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

Each case starts with a blank line. The next line will contain two integers: n (1 ≤ n ≤ 100) and m (0 ≤ m ≤ n*(n-1)/2), indicating the number of nodes and the number of roads respectively. The next m lines, each will contain two integers a b (1 ≤ a, b ≤ n, a ≠ b) indicating that there is a road between node a and b. All the given roads will be distinct.

For each case, print the case number and number of nodes that can be entered by Hanzo, carrying Nakururu with him.