You are given a tree (a connected graph with no cycles), and then the edges in the tree are made directional; your task is to add minimum number of special paths in the tree such that it's possible to go from one node to another. The rules for the special paths are noted below:

1. A special path starts in a node, consists of some continuous edges and nodes and also ends in a node.
2. In a special path, the edges should be in opposite directions as they are in the tree.
3. A node or an edge can be visited at most once in a special path.
4. Multiple special paths may have common nodes or edges.

For example, in the given picture, a tree is drawn, the black arrows represent the edges and their directions, circles represent nodes. Then we need two special paths. One path is 2-1-0 (green arrow), another is 3-1-4 (blue arrow). Another valid option is to use paths 3-1-4 and 2-1-4. You cannot add a path like 1-3 or 0-1-2 because of rule 2. You cannot add 0-2 or 2-3-0 because of rule 1.

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

Each case starts with a line containing an integer N (2 ≤ N ≤ 20000), where N denotes the number of nodes. The nodes are numbered from 0 to N-1. Each of the next N-1 lines contains two integers u v (0 ≤ u, v < N, u ≠ v) meaning that there is an edge from u to v.

For each case, print the case number and the minimum number of special paths required such that it's possible to go from any node to another.

Dataset is huge, use faster I/O methods.