D1. Tree Queries (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe 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.InputEach 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.OutputFor each test case print a single nonnegative integer, the minimum number of queries you need, on its own line.ExampleInput
3
1
2
1 2
10
2 4
2 1
5 7
3 10
8 6
6 1
1 3
4 7
9 6
Output
0
1
2
NoteIn 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.
3
1
2
1 2
10
2 4
2 1
5 7
3 10
8 6
6 1
1 3
4 7
9 6

0 1 2 
['brute force', 'constructive algorithms', 'dfs and similar', 'dp', 'greedy', 'trees', '*2200']