Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

You are given a rooted tree consisting of N nodes. The nodes are numbered from 1 to N, and node 1 is the root. At each node of the tree, you can put zero or one coin such that the following property is satisfied for the tree:

For each node of the tree, starting from the original configuration, we should be able to get two coins on the node by applying at most two operations of the following kind:
Take a coin from a node and move it to an adjacent node.

While trying to get to a particular node, if the same coin is moved in two operations, both those operations should either be towards the root, or both of them should be away from the root. That is, you cannot move a coin to its parent in one operation and then take it to another child of the parent in the second operation.

Find the minimum total number of coins which can be used to get a valid configuration.

------ Input ------

The first line of the input contains an integer T.
For each test case, the first line contains an integer N.
Each of the next N - 1 lines, contains two space separated integers u, v, denoting that there is an edge between node u and node v of the tree.

------ Output ------

For each test case, output a single integer corresponding to the minimum number of coins that can be used. If it's not possible to achieve this, output -1.

------ Constraints ------

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ u, v ≤ N$

------ Subtasks ------

Subtask #1 (40 points)

$1 ≤ N ≤ 1000$

Subtask #2 (60 points)

$Original constraints$

----- Sample Input 1 ------
2

3

1 2

1 3

5

1 2

1 3

3 4

3 5
----- Sample Output 1 ------
3

4
----- explanation 1 ------
Example case 1.

The nodes which have a coin in them are shown by blue color. You can see that each node satisfies the desired property.

Example case 2.

见题面

见题面