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 \le t \le 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 \le n \le 2 \cdot 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 \le u, v \le n$, $u \neq 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 \cdot 10^5$.


-----Output-----

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


-----Examples-----

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 a bud vertex $4$ and re-hang it to vertex $3$. After that you can choose a bud vertex $2$ and re-hang it to vertex $7$. As a result, you will have the following tree with $2$ leaves:

It can be proved that it is the minimal number of leaves possible to get.

In the second test case the tree looks as follows:

You can choose a bud vertex $3$ and re-hang it to vertex $5$. As a result, you will have the following tree with $2$ leaves:

It can be proved that it is the minimal number of leaves possible to get.

Difficulty: HARD
Tags: Graph traversal

Constructive algorithms

Greedy algorithms

Tree algorithms

Dynamic programming
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
def naiveSolve():
	return

def solve():
	return

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		n = int(input())
		adj = [[] for _ in range(n + 1)]
		for __ in range(n - 1):
			(u, v) = readIntArr()
			adj[u].append(v)
			adj[v].append(u)
		par = [-1 for __ in range(n + 1)]
		childCnts = [0 for __ in range(n + 1)]
		depth = [-1 for __ in range(n + 1)]
		depth[1] = 0
		stack = [(1, -1)]
		while stack:
			(node, p) = stack.pop()
			par[node] = p
			for nex in adj[node]:
				if nex != p:
					childCnts[node] += 1
					stack.append((nex, node))
					depth[nex] = depth[node] + 1
		nodeDepths = [(depth[node], node) for node in range(1, n + 1)]
		nodeDepths.sort(reverse=True)
		pruned = [False] * (n + 1)
		budCnts = 0
		for (depth, node) in nodeDepths:
			if depth >= 2 and pruned[node] == False and (pruned[par[node]] == False):
				budCnts += 1
				twoUp = par[par[node]]
				childCnts[twoUp] -= 1
				pruned[par[node]] = True
		directLeaves = childCnts[1]
		budContribution = n - 1 - directLeaves - budCnts * 2
		leavesWithoutBud = max(1, directLeaves)
		ans = leavesWithoutBud + budContribution
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys
input = sys.stdin.readline
for i in range(int(input())):
	n = int(input())
	g = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	i = 0
	q = [1]
	p = [None] * (n + 1)
	w = [True] * (n + 1)
	r = 0
	while i < len(q):
		x = q[i]
		P = p[x]
		i += 1
		for v in g[x]:
			if v != P:
				q.append(v)
				p[v] = x
	for i in range(len(q) - 1, 0, -1):
		x = q[i]
		P = p[x]
		c = len([1 for v in g[x] if v != P and w[v]])
		if c != 0:
			r += c - 1
			w[x] = False
	c = len([v for v in g[1] if w[v]])
	print(r + 1) if c == 0 else print(r + c)


from collections import deque
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.setrecursionlimit(200010)

def judgebuds(children, buds, seq):
	for index in seq:
		if not children[index]:
			continue
		for nextindex in children[index]:
			if not buds[nextindex]:
				buds[index] = True
				break

def main(t):
	n = int(input())
	neigh = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		neigh[u - 1].append(v - 1)
		neigh[v - 1].append(u - 1)
	children = [[] for i in range(n)]
	queue = deque()
	queue.append(0)
	visited = [False] * n
	visited[0] = True
	seq = []
	while queue:
		index = queue.popleft()
		seq.append(index)
		for nextindex in neigh[index]:
			if visited[nextindex]:
				continue
			visited[nextindex] = True
			children[index].append(nextindex)
			queue.append(nextindex)
	seq = seq[::-1]
	buds = [False] * n
	judgebuds(children, buds, seq)
	ans = n
	for i in range(1, n):
		if buds[i]:
			ans -= 2
	if buds[0]:
		ans -= 1
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


import sys
from collections import defaultdict
input = sys.stdin.readline
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = False

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def minus_one(arr):
	return [x - 1 for x in arr]

def minus_one_matrix(mrr):
	return [[x - 1 for x in row] for row in mrr]
BUFSIZE = 8192
import os
from io import BytesIO, IOBase

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					if stack:
						stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def solve_():
	k = int(input())
	mrr = read_matrix(k - 1)
	g = defaultdict(set)
	for (a, b) in mrr:
		g[a].add(b)
		g[b].add(a)
	visited = set()

	@bootstrap
	def is_bud(cur):
		total_count_buds = 0
		total_children_not_a_bud = 0
		num_children = 0
		num_children_is_bud = 0
		for nex in g[cur]:
			if nex in visited:
				continue
			visited.add(nex)
			(child_is_bud, count_buds, children_not_a_bud) = (yield is_bud(nex))
			num_children += 1
			total_count_buds += count_buds
			total_children_not_a_bud += children_not_a_bud
			if child_is_bud:
				num_children_is_bud += 1
		if num_children == 0 or num_children == num_children_is_bud:
			yield (False, total_count_buds, total_children_not_a_bud + (num_children - num_children_is_bud))
		yield (True, total_count_buds + 1, total_children_not_a_bud + (num_children - num_children_is_bud))
	visited.add(1)
	(_, total_count_buds, total_children_not_a_bud) = is_bud(1)
	return total_children_not_a_bud - total_count_buds + 1
for case_num in range(int(input())):
	res = solve()
	print(res)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	adj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	leaf = 0
	bud = 0
	below = [0] * n
	stack = [0]
	vis = [False] * n
	vis[0] = True
	par = [-1] * n
	while stack:
		cur = stack[-1]
		if adj[cur]:
			nex = adj[cur].pop()
			if not vis[nex]:
				vis[nex] = True
				par[nex] = cur
				stack.append(nex)
		else:
			if below[cur] == 0:
				leaf += 1
				if cur:
					below[par[cur]] += 1
			elif cur:
				bud += 1
			stack.pop()
	print(leaf - bud)


import sys
BUFSIZE = 8192
import os
from io import BytesIO, IOBase

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]
all_res = []
cases = []
for case_num in range(int(input())):
	k = int(input())
	mrr = read_matrix(k - 1)
	g = [[] for i in range(k + 2)]
	for (a, b) in mrr:
		g[a].append(b)
		g[b].append(a)
	visited = set()
	total_children_not_a_bud = 0
	total_count_buds = 0
	has_children = [False for _ in range(k + 2)]
	has_children_who_are_not_buds = [False for _ in range(k + 2)]
	start = 1
	entered = set([start])
	exiting = set()
	stack = [start]
	prevs = {start: 0}
	while stack:
		cur = stack[-1]
		if cur in exiting:
			stack.pop()
			if cur in prevs:
				prev = prevs[cur]
				if has_children[cur] and has_children_who_are_not_buds[cur]:
					total_count_buds += 1
				else:
					has_children_who_are_not_buds[prev] = True
					if cur != 1:
						total_children_not_a_bud += 1
				has_children[prev] = True
			continue
		for nex in g[cur]:
			if nex in entered:
				continue
			entered.add(nex)
			stack.append(nex)
			prevs[nex] = cur
		exiting.add(cur)
	res = total_children_not_a_bud - total_count_buds + 1
	all_res.append(res)
all_res = '\n'.join((str(x) for x in all_res))
print(all_res)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	edges = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		edges[u - 1].append(v - 1)
		edges[v - 1].append(u - 1)
	(pare, fills, pendent, nivells) = ({0: None}, [set() for _ in range(n)], [0], [])
	while pendent:
		nou_pendent = []
		for p in pendent:
			for f in edges[p]:
				if f != pare[p]:
					pare[f] = p
					fills[p].add(f)
					nou_pendent.append(f)
		pendent = nou_pendent
		nivells.append(pendent)
	buds = []
	for nivell in reversed(nivells):
		for b in nivell:
			if len(fills[b]) > 0 and all((len(fills[f]) == 0 for f in fills[b])):
				buds.append(len(fills[b]))
				p = pare[b]
				fills[p].remove(b)
	ans = max(len(fills[0]), 1)
	for b in buds:
		ans += b - 1
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	adj = [[] for _ in range(n)]
	parent = [0] * n
	ifBuds = [False] * n
	visited = [False] * n
	visited[0] = True
	numBuds = 0
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	stack = [0]
	while stack:
		vertice = stack[-1]
		if adj[vertice]:
			nextVertice = adj[vertice].pop()
			if not visited[nextVertice]:
				visited[nextVertice] = True
				parent[nextVertice] = vertice
				stack.append(nextVertice)
		else:
			if ifBuds[vertice]:
				if vertice:
					numBuds += 1
			elif vertice:
				ifBuds[parent[vertice]] = True
			stack.pop()
	print(n - 2 * numBuds - (1 if ifBuds[0] else 0))


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(3 * 10 ** 5)
import threading
inp = lambda : list(map(int, input().split()))

def dfs(p, prev):
	(turn, count_buds, count_leaves) = (0, 0, 0)
	for i in child[p]:
		if i == prev:
			continue
		x = dfs(i, p)
		turn = max(x[0], turn)
		count_buds += x[1]
		count_leaves += x[2]
	if turn == 1:
		count_buds += 1
	else:
		count_leaves += 1
	return [turn ^ 1, count_buds, count_leaves]

def main():
	global child
	for T in range(int(input())):
		n = int(input())
		child = [[] for i in range(n + 1)]
		for i in range(n - 1):
			(u, v) = inp()
			child[u].append(v)
			child[v].append(u)
		(turn, buds, leaves) = dfs(1, -1)
		if turn == 0:
			buds -= 1
		else:
			leaves -= 1
		if turn == 0:
			ans = leaves - buds
		else:
			ans = leaves - buds + 1
		print(ans)
threading.stack_size(10 ** 8)
threading.Thread(target=main).start()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
	n = int(input())
	G = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		G[u].append(v)
		G[v].append(u)
	isBud = [False] * n
	root = 0
	vis = [False] * n
	stk = [(root, -1)]
	while stk:
		(node, par) = stk[-1]
		if not vis[node]:
			vis[node] = True
			for node0 in G[node]:
				if node0 != par:
					stk.append((node0, node))
		else:
			stk.pop()
			for node0 in G[node]:
				if node0 != par and (not isBud[node0]):
					isBud[node] = True
	isBud[root] = False
	buds = sum(isBud)
	for node in G[root]:
		if not isBud[node]:
			print(n - 2 * buds - 1)
			return
	print(n - 2 * buds)
	return
for nt in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
from collections import deque

def is_buds(x):
	if x == 1:
		return (False, None)
	tmp = [x]
	if not children[x]:
		return (False, None)
	for c in children[x]:
		tmp.append(c)
		if children[c]:
			return (False, None)
	return (True, tmp)
(T,) = map(int, input().split())
for tt in range(T):
	(N,) = map(int, input().split())
	G = [[] for _ in range(N + 1)]
	for _ in range(N - 1):
		(u, v) = map(int, input().split())
		G[u].append(v)
		G[v].append(u)
	vs = set([1])
	ll = []
	queue = deque([1])
	parents = [0] * (N + 1)
	children = [set() for _ in range(N + 1)]
	ll.append(v)
	while queue:
		v = queue.popleft()
		for u in G[v]:
			if u in vs:
				continue
			parents[u] = v
			children[v].add(u)
			ll.append(u)
			vs.add(u)
			queue.append(u)
	RR = 0
	fll = [0] * (N + 1)
	for i in range(1, N + 1):
		if not children[i]:
			RR += 1
			fll[i] = 1
	ll = ll[::-1]
	vs = set()
	R = 0
	for x in ll:
		if x in vs:
			continue
		(f, l) = is_buds(parents[x])
		if not f:
			continue
		for u in l:
			vs.add(u)
		children[parents[parents[x]]].remove(parents[x])
		if children[parents[parents[x]]]:
			R += 1
	f = 1
	for i in range(1, N + 1):
		if i not in vs and (not children[i]) and fll[i]:
			f = 0
	print(RR - R)


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

def inp():
	return int(input())

def input_list():
	return list(map(int, input().split()))

def input_string():
	s = input()
	return list(s[:len(s) - 1])

def input_int_gen():
	return map(int, input().split())
from collections import defaultdict, deque
tests = inp()
for _ in range(tests):
	n = inp()
	children = [set() for _ in range(n + 1)]
	bud_dict = [0 for _ in range(n + 1)]
	heights = [1 for _ in range(n + 1)]
	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()
		children[cur].discard(grand)
		adjs = children[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
	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)


import sys, math
from collections import Counter, defaultdict, deque
input = sys.stdin.buffer.readline
T = int(input())
for _ in range(T):
	n = int(input())
	e = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		e[a].append(b)
		e[b].append(a)
	(par, order) = ([0] * (n + 1), [])
	q = deque([1])
	while q:
		u = q.popleft()
		order.append(u)
		for v in e[u]:
			if par[u] == v:
				continue
			par[v] = u
			q.append(v)
	(s, res) = (defaultdict(int), 0)
	(NORMAL, REMOVABLE, REMOVED) = (0, 1, 2)
	for u in reversed(order):
		(stat, cc) = (REMOVABLE, 0)
		for v in e[u]:
			if par[u] == v:
				continue
			if s[v] == NORMAL:
				stat = NORMAL
			elif s[v] == REMOVABLE:
				cc += 1
		if stat == REMOVABLE and cc > 0:
			stat = REMOVED
		s[u] = stat
		if u == 1:
			res += cc + (stat == REMOVABLE)
		elif stat == NORMAL:
			res += cc
		elif stat == REMOVED:
			res += cc - 1
	print(res)


import sys
input = iter(sys.stdin.read().splitlines()).__next__

def root_tree(root, tree):
	parents = [None] * len(tree)
	stack = [root]
	while stack:
		node = stack.pop()
		for child in tree[node]:
			parents[child] = node
			tree[child].remove(node)
			stack.append(child)
	return parents

def solve():
	n = int(input())
	graph = [set() for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		graph[u].add(v)
		graph[v].add(u)
	parents = root_tree(0, graph)
	leaves = list(filter(lambda i: len(graph[i]) == 0, range(n)))
	num_leaves = len(leaves)
	num_leaf_children = [0] * n
	for leaf in leaves:
		num_leaf_children[parents[leaf]] += 1
	buds = [node for node in range(1, n) if len(graph[node]) > 0 and len(graph[node]) == num_leaf_children[node]]
	num_buds = 0
	while buds:
		num_buds += 1
		node = buds.pop()
		parent = parents[node]
		graph[parent].remove(node)
		if parent == 0:
			if len(graph[parent]) == 0:
				num_leaves += 1
		elif len(graph[parent]) == 0:
			grandparent = parents[parent]
			num_leaf_children[grandparent] += 1
			num_leaves += 1
			if grandparent != 0 and num_leaf_children[grandparent] == len(graph[grandparent]):
				buds.append(grandparent)
		elif len(graph[parent]) == num_leaf_children[parent]:
			buds.append(parent)
	return num_leaves - num_buds
t = int(input())
output = []
for _ in range(t):
	output.append(solve())
print(*output, sep='\n')


def naiveSolve():
	return

def solve():
	return
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		n = int(input())
		adj = [[] for _ in range(n + 1)]
		for __ in range(n - 1):
			(u, v) = readIntArr()
			adj[u].append(v)
			adj[v].append(u)
		pruned = [False] * (n + 1)
		budCnts = [0]
		childCnts = [0] * (n + 1)

		@bootstrap
		def dfs(node):
			for nex in adj[node]:
				if not (len(path) >= 2 and nex == path[-2]):
					childCnts[node] += 1
					path.append(nex)
					yield dfs(nex)
					path.pop()
			if len(path) >= 3 and pruned[node] == pruned[path[-2]] == False:
				budCnts[0] += 1
				pruned[path[-2]] = True
				childCnts[path[-3]] -= 1
			yield None
		path = [1]
		dfs(1)
		budCnts = budCnts[0]
		directLeaves = childCnts[1]
		budContribution = n - 1 - directLeaves - budCnts * 2
		leavesWithoutBud = max(1, directLeaves)
		ans = leavesWithoutBud + budContribution
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict
from math import ceil, floor, sqrt, log2, gcd, pi
from heapq import heappush, heappop
from bisect import bisect_left, bisect
import sys
abc = 'abcdefghijklmnopqrstuvwxyz'
ABC = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for _ in range(int(input())):
	n = int(input())
	adj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	below = [0] * n
	vis = [False] * n
	vis[0] = True
	stack = [0]
	par = [-1] * n
	leaves = 0
	buds = 0
	while stack:
		curr = stack[-1]
		if adj[curr]:
			val = adj[curr].pop()
			if not vis[val]:
				vis[val] = True
				par[val] = curr
				stack.append(val)
		else:
			if below[curr] == 0:
				leaves += 1
				if curr:
					below[par[curr]] += 1
			elif curr:
				buds += 1
			stack.pop()
	print(leaves - buds)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
for _ in range(int(input())):
	N = int(input())
	edge = [[] for i in range(N)]
	for i in range(N - 1):
		(u, v) = mi()
		edge[u - 1].append(v - 1)
		edge[v - 1].append(u - 1)
	deq = deque([0])
	parent = [-1 for v in range(N)]
	topo = []
	while deq:
		v = deq.popleft()
		topo.append(v)
		for nv in edge[v]:
			if nv != parent[v]:
				parent[nv] = v
				deq.append(nv)
	leaf = [False for v in range(N)]
	bud_cnt = [0 for v in range(N)]
	res = 0
	for v in topo[::-1]:
		if v != 0 and len(edge[v]) == 1:
			res += 1
			leaf[v] = True
			continue
		for nv in edge[v]:
			if nv != parent[v]:
				bud_cnt[v] += bud_cnt[nv]
		if any((leaf[nv] and nv != parent[v] for nv in edge[v])):
			bud_cnt[v] += 1
		else:
			leaf[v] = True
			bud_cnt[v] -= 1
	minus = 0
	bud_cnt[0] = 0
	for v in topo:
		if v != 0 and len(edge[v]) == 1:
			minus = max(minus, bud_cnt[v])
		else:
			S = sum((bud_cnt[nv] for nv in edge[v] if nv != parent[v]))
			for nv in edge[v]:
				if nv != parent[v]:
					bud_cnt[nv] = bud_cnt[v] + S - bud_cnt[nv]
	print(res - minus)


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	n = int(input())
	E = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		E[u].append(v)
		E[v].append(u)
	ROOT = 0
	QUE = [ROOT]
	Parent = [-1] * (n + 1)
	Parent[ROOT] = n
	TOP_SORT = []
	Child = [[] for i in range(n)]
	while QUE:
		x = QUE.pop()
		TOP_SORT.append(x)
		for to in E[x]:
			if Parent[to] == -1:
				Parent[to] = x
				Child[x].append(to)
				QUE.append(to)
	DEG = [0] * n
	L = [0] * n
	ANS = []
	for x in TOP_SORT[::-1]:
		if DEG[x] == len(Child[x]):
			L[x] = 1
			continue
		sc = 0
		for ch in Child[x]:
			if L[ch] == 1:
				sc += 1
		if sc != 0:
			ANS.append(sc)
		if x != 0 and Parent[x] != 0:
			DEG[Parent[x]] += 1
	LANS = ANS[0]
	for i in range(1, len(ANS)):
		LANS += ANS[i] - 1
	print(LANS)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def dfs(graph, start=0):
	n = len(graph)
	dp = [0] * n
	(visited, finished) = ([False] * n, [False] * n)
	stack = [start]
	while stack:
		start = stack[-1]
		if not visited[start]:
			visited[start] = True
			for child in graph[start]:
				if not visited[child]:
					stack.append(child)
		else:
			stack.pop()
			dp[start] += 1
			for child in graph[start]:
				if finished[child]:
					dp[start] += dp[child]
			if dp[start] > 1:
				dp[start] = 0
			finished[start] = True
	return dp

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		tree = [[] for _ in range(n)]
		for _ in range(n - 1):
			(u, v) = map(int, input().split())
			tree[u - 1].append(v - 1)
			tree[v - 1].append(u - 1)
		dp = dfs(tree)
		print(sum([1 if i == 1 else -1 for i in dfs(tree)]) + (dp[0] == 0))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import deque

def solve():
	n = int(input())
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		g[x].append(y)
		g[y].append(x)
	v = [0] * n
	c = [set() for i in range(n)]
	p = [0 for i in range(n)]
	L = []
	queue = deque()
	queue.append(0)
	while queue:
		x = queue.popleft()
		L.append(x)
		v[x] = 1
		for y in g[x]:
			if v[y] == 0:
				p[y] = x
				c[x].add(y)
				queue.append(y)
	L = L[::-1]
	L.pop()
	m = m2 = m3 = ans = 0
	for x in L:
		if c[x]:
			m3 += 1
			m += len(c[x])
			c[p[x]].remove(x)
		elif p[x] == 0:
			m2 += 1
	if m2:
		return m2 + m - m3
	return m + 1 - m3
import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
for i in range(t):
	print(solve())