human
What is a Python program to print a single integer — the minimal number of leaves that is possible to get after some operations given the following:
A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a vertex v (different from root) is the previous to v vertex on the shortest path from the root to the vertex v. Children of the vertex v are all vertices for which v is the parent.

A vertex is a leaf if it has no children. We call a vertex a bud, if the following three conditions are satisfied: 

  * it is not a root, 
  * it has at least one child, and 
  * all its children are leaves. 


You are given a rooted tree with n vertices. The vertex 1 is the root. In one operation you can choose any bud with all its children (they are leaves) and re-hang them to any other vertex of the tree. By doing that you delete the edge connecting the bud and its parent and add an edge between the bud and the chosen vertex of the tree. The chosen vertex cannot be the bud itself or any of its children. All children of the bud stay connected to the bud.

What is the minimum number of leaves it is possible to get if you can make any number of the above-mentioned operations (possibly zero)?

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of the vertices in the given tree.

Each of the next n-1 lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) meaning that there is an edge between vertices u and v in the tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of n over all test cases doesn't exceed 2 ⋅ 10^5.

Output

For each test case print a single integer — the minimal number of leaves that is possible to get after some operations.

Example

Input

5
7
1 2
1 3
1 4
2 5
2 6
4 7
6
1 2
1 3
2 4
2 5
3 6
2
1 2
7
7 3
1 5
1 3
4 6
4 7
2 1
6
2 1
2 3
4 5
3 4
3 6

Output

2
2
1
2
1

Note

In the first test case the tree looks as follows:


Firstly you can choose...
assistant
#Here is Python program to print a single integer — the minimal number of leaves that is possible to get after some operations.

from os import write
import sys
input = sys.stdin.readline

############ ---- Input Functions ---- ############
def inp(): 
    # one integer
    return int(input())
def input_list():
    # list of integers
    return list(map(int,input().split()))
def input_string():
    # list of characters
    s = input()
    return list(s[:len(s) - 1])
def input_int_gen():
    # integer generator 
    return map(int,input().split())

# Codeforces Global Round 16 E
from collections import defaultdict, deque
tests = inp()
for _ in range(tests):
    n = inp()
    children = [set() for _ in range(n+1)]
    # parent = [-1 for _ in range(n+1)]
    bud_dict = [0 for _ in range(n+1)]
    heights = [1 for _ in range(n+1)] # 1 leaf 2 bud
    for _ in range(n-1):
        a, b = input_int_gen()
        children[a].add(b)
        children[b].add(a)
    bfs_queue = deque([(1, 1)])
    while bfs_queue:
        cur, grand = bfs_queue.pop()
        # grand = parent[cur]
        children[cur].discard(grand)
        adjs = children[cur]
        # for adj in adjs:
        #     parent[adj] = cur
        bfs_queue.extendleft([(x, cur) for x in adjs])
    def write_height(i):
        for child in children[i]:
            write_height(child)
            if heights[child] == 1:
                heights[i] = 2
    ############ tree complete ##########

    # write_height(1)
    # using post-order traversal
    # python recursion is expensive (TLE / MLE)

    stk = [(1, False)]
    while stk:
        cur, visited = stk.pop()
        cs = children[cur]
        if not cs:
            continue
        if visited:
            if any(heights[x] == 1 for x in cs):
                heights[cur] = 2
        else:
            stk.append((cur, True))
            stk.extend((x, False) for x in cs)

    n_buds = heights.count(2)
    n_leaves = heights.count(1) - 1
    
    if heights[1] == 2:
        n_buds -= 1
    print(n_leaves - n_buds)