E. Tree of Life
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In the heart of an ancient kingdom grows the legendary Tree of Life — the only one of its kind and the source of magical power for the entire world. The tree consists of $$$n$$$ nodes. Each node of this tree is a magical source, connected to other such sources through magical channels (edges). In total, there are $$$n-1$$$ channels in the tree, with the $$$i$$$-th channel connecting nodes $$$v_i$$$ and $$$u_i$$$. Moreover, there exists a unique simple path through the channels between any two nodes in the tree.

However, the magical energy flowing through these channels must be balanced; otherwise, the power of the Tree of Life may disrupt the natural order and cause catastrophic consequences. The sages of the kingdom discovered that when two magical channels converge at a single node, a dangerous "magical resonance vibration" occurs between them. To protect the Tree of Life and maintain its balance, it is necessary to select several paths and perform special rituals along them. A path is a sequence of distinct nodes $$$v_1, v_2, \ldots, v_k$$$, where each pair of adjacent nodes $$$v_i$$$ and $$$v_{i+1}$$$ is connected by a channel. When the sages perform a ritual along such a path, the resonance vibration between the channels $$$(v_i, v_{i+1})$$$ and $$$(v_{i+1}, v_{i+2})$$$ is blocked for each $$$1 \leq i \leq k - 2$$$.

The sages' task is to select the minimum number of paths and perform rituals along them to block all resonance vibrations. This means that for every pair of channels emanating from a single node, there must exist at least one selected path that contains both of these channels.

Help the sages find the minimum number of such paths so that the magical balance of the Tree of Life is preserved, and its power continues to nourish the entire world!

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 4 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) — the number of nodes in the Tree of Life.

The $$$i$$$-th of the following $$$n - 1$$$ lines of each test case contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \leq v_i < u_i \leq n$$$) — the channel connecting nodes $$$v_i$$$ and $$$u_i$$$.

It is guaranteed that there exists a unique simple path through the channels between any two nodes.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum number of paths that the sages need to select to prevent a catastrophe.

Example
Input
5
4
1 2
2 3
3 4
2
1 2
4
1 2
1 3
1 4
8
3 7
2 4
1 2
2 5
3 6
1 3
3 8
6
2 3
1 2
3 6
1 5
1 4
Output
1
0
3
7
3
Note

In the first test case, there are two pairs of channels emanating from a single node: $$$(1, 2)$$$ and $$$(2, 3)$$$, $$$(2, 3)$$$ and $$$(3, 4)$$$. It is sufficient to perform the ritual along the path $$$1-2-3-4$$$. Thus, the answer is $$$1$$$.

In the second test case, there are no pairs of channels emanating from a single node, so the answer is $$$0$$$.

In the third test case, rituals can be performed along the paths $$$2-1-3$$$, $$$2-1-4$$$, and $$$3-1-4$$$.