403292: GYM101102 L Starry Night

L. Starry Nighttime limit per test6 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Reem likes to look up into the night sky and count how many stars there are. The sky is represented as a tree, and a star is a fixed node with three or more rays of possibly varying lengths leading out of it. A ray is a chain of connected nodes where each node except for the last one is connected to exactly two nodes, and the last one is connected to exactly one node.

If Reem can remove as many nodes as she wants, what is the maximum number of stars she can get in a given sky?Input

The first line of input contains a single integer T, the number of test cases.

The first line of each test case contains a single integers N (1 ≤ N ≤ 10⁵), the number of nodes in the sky.

Each of the next N - 1 lines contains two integers a and b (1 ≤ a, b ≤ N), and represents a link that connects two nodes.

It is guaranteed that the given graph is a tree.

Output

For each test case, print the maximum number of stars Reem can get after removing zero or more nodes, on a single line.

ExampleInput

1
9
1 2
3 2
5 1
3 7
1 4
3 8
1 6
3 9

Output

2

Note

A tree is an undirected graph with exactly one path between any two nodes.