Description: The only difference between this problem and D2 is the bound on the size of the tree. You are given an unrooted tree with $$$n$$$ vertices. There is some hidden vertex $$$x$$$ in that tree that you are trying to find. To do this, you may ask $$$k$$$ queries $$$v_1, v_2, \ldots, v_k$$$ where the $$$v_i$$$ are vertices in the tree. After you are finished asking all of the queries, you are given $$$k$$$ numbers $$$d_1, d_2, \ldots, d_k$$$, where $$$d_i$$$ is the number of edges on the shortest path between $$$v_i$$$ and $$$x$$$. Note that you know which distance corresponds to which query. What is the minimum $$$k$$$ such that there exists some queries $$$v_1, v_2, \ldots, v_k$$$ that let you always uniquely identify $$$x$$$ (no matter what $$$x$$$ is). Note that you don't actually need to output these queries. Input Format: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows. The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the number of vertices in the tree. Each of the next $$$n-1$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$), meaning there is an edges between vertices $$$x$$$ and $$$y$$$ in the tree. It is guaranteed that the given edges form a tree. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$. Output Format: For each test case print a single nonnegative integer, the minimum number of queries you need, on its own line. Note: In the first test case, there is only one vertex, so you don't need any queries. In the second test case, you can ask a single query about the node $$$1$$$. Then, if $$$x = 1$$$, you will get $$$0$$$, otherwise you will get $$$1$$$.