Infected Tree

Description:

Input:

There are several test cases in the input data. The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 5000$$$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $$$n$$$ ($$$2\leq n\leq 3\cdot 10^5$$$) — the number of vertices of the tree.

The $$$i$$$-th of the following $$$n-1$$$ lines in the test case contains two positive integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), meaning that there exists an edge between them in the graph.

It is guaranteed that the graph is a binary tree rooted at $$$1$$$. It is also guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$3\cdot 10^5$$$.

Output:

For each test case, output the maximum number of vertices Misha can save.

Sample Input:

4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15

Sample Output:

0
2
2
10

Note:

In the first test case, the only possible action is to delete vertex $$$2$$$, after which we save $$$0$$$ vertices in total.

In the second test case, if we delete vertex $$$2$$$, we can save vertices $$$3$$$ and $$$4$$$.