You are given a tree (a connected graph with no cycles), and the edges of the tree which are for some reason directed; your task is to add \textbf{minimum} number of special paths in the tree such that it's possible to go from any node to another. The rules for the special paths are noted below: \begin{enumerate} \item A special path consists of some continuous edges (from the tree) and nodes. \item In a special path, the edges should be in opposite directions as they are in the tree. \item A node or an edge can be visited at most once in a special path. \item Multiple special paths may have common nodes or edges. \end{enumerate} For example, in the picture below, 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 \textbf{2-1-0} (green arrow), another is \textbf{3-1} (blue arrow). Instead of the path \textbf{3-1} we can add \textbf{3-1-0}. You cannot add a path like \textbf{1-3} or \textbf{0-1-2} because of rule 2. You cannot add \textbf{0-2} or \textbf{2-3-0} because of rule 1. \includegraphics{https://static.e-olymp.com/content/6a/6a81043b679c419db07d00c284ae29b1d939d769.jpg} \InputFile Input starts with an integer \textbf{T (≤ 30)}, denoting the number of test cases. Each case starts with a line containing an integer \textbf{N (2 ≤ N ≤ 20000)}, where \textbf{N} denotes the number of nodes. The nodes are numbered from \textbf{0} to \textbf{N-1}. Each of the next \textbf{N-1} lines contains two integers \textbf{u v (0 ≤ u, v < N, u ≠ v)} meaning that there is an edge from \textbf{u} to \textbf{v}. \OutputFile 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.