The country of Byteland contains $N$ cities and $N-1$ bidirectional roads. There is a path between any two cities. The roads in Byteland were built long ago, and now they are in need of repair. You have been hired to fix all the roads. You intend to do this by dispatching robots on some of the roads. Each robot will repair the road he is currently on and then moves to one of the adjacent unrepaired roads. After repairing that, it will move to another adjacent unrepaired road, repair that and so on.

Two roads are adjacent if they have the same city at one of their endpoints. For the process to be efficient, no two robots will ever repair the same road, and no road can be visited twice. What is the minimum number of robots needed to accomplish the task?

Input Format

The first line contains the number of test cases $\mathbf{T}$. $\mathbf{T}$ test cases follow. The first line of each test case contains $N$, the number of cities in Byteland. The cities are numbered $\textbf{0.N-1}$. The following $N-1$ lines contain the description of the roads. The $i^{\mbox{th}}$ line contains two integers $a_i$ and $b_i$, meaning that there is a road connecting cities with numbers $a_i$ and $b_i$.

Constraints

$1\leq T\leq20$  
$1\leq N\leq10000$  
$0\leq a_i,b_i<N$

Output Format

Print $\mathbf{T}$ lines, one corresponding to each test case containing the required answer for that test case.

Sample Input
3  
4  
0 1  
0 2  
0 3  
6  
0 1  
1 2  
2 3  
2 4  
4 5  
7  
0 1  
1 2  
2 3  
2 4  
4 5  
3 6

Sample Output
1  
1  
2

Explanation

For the first case, one robot is enough to repair all roads: $(0,1)\rightarrow(0,2)\rightarrow(0,3)$ 

For the second case, one robot is again enough: $(0,1)\to(1,2)\to(2,3)\to(2,4)\to(4,5)$ 

The the third case, there is no way to repair all the roads with one robot and at least two are needed.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Graph algorithms


Solutions:
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


def ile(mst, i, gleb=0):
	st = mst[i]
	if len(st) == 0:
		return (0, False)
	sum = 0
	bylniep = False
	bylpodniep = False
	for x in st:
		mst[x].remove(i)
		(v, bn) = ile(mst, x, gleb + 1)
		mst[x].add(i)
		if v % 2 == 1:
			bylniep = True
		if v % 2 == 0 and (not bn):
			bylpodniep = True
		sum += v
	if not bylniep and bylpodniep:
		sum += 1
	return (sum, bylniep)
prob = int(input())
for pr in range(prob):
	n = int(input())
	miasta = [set() for _ in range(n)]
	for p in range(n - 1):
		pol = input().split()
		if pol[0] == '#':
			continue
		p0 = int(pol[0])
		p1 = int(pol[1])
		miasta[p0].add(p1)
		miasta[p1].add(p0)
	mn = 9999
	for q in range(n):
		(v, n) = ile(miasta, q)
		if v % 2 == 1:
			v += 1
		if v < mn:
			mn = v
		break
	print(mn // 2)


T = int(input())
for _ in range(T):
	N = int(input())
	G = [[] for _ in range(N)]
	for _ in range(N - 1):
		(u, v) = map(int, input().split())
		(u, v) = (u, v)
		G[u].append(v)
		G[v].append(u)
	visited = [False] * N

	def dfs(n):
		visited[n] = True
		(r, l1, l2) = (0, 0, 0)
		for adj in G[n]:
			if visited[adj]:
				continue
			(r1, l) = dfs(adj)
			r += r1
			if l == 1:
				l1 += 1
			if l == 2:
				l2 += 1
		if l2 == 0:
			if l1 == 0:
				return (r, 1)
			else:
				return (r, 2)
		elif l2 % 2 == 0:
			return (r + l2 // 2, 0)
		else:
			return (r + l2 // 2, 2)
	(r, l) = dfs(0)
	if l == 2:
		r += 1
	print(r)


T = int(input())
for _ in range(T):
	N = int(input())
	G = [[] for _ in range(N)]
	for _ in range(N - 1):
		(u, v) = map(int, input().split())
		(u, v) = (u, v)
		G[u].append(v)
		G[v].append(u)
	visited = [False] * N

	def dfs(n):
		visited[n] = True
		(r, l1, l2) = (0, 0, 0)
		for adj in G[n]:
			if visited[adj]:
				continue
			(r1, l) = dfs(adj)
			r += r1
			if l == 1:
				l1 += 1
			if l == 2:
				l2 += 1
		if l2 == 0:
			if l1 == 0:
				return (r, 1)
			else:
				return (r, 2)
		elif l2 % 2 == 0:
			return (r + l2 // 2, 0)
		else:
			return (r + l2 // 2, 2)
	(r, l) = dfs(0)
	if l == 2:
		r += 1
	print(r)


T = int(input())
for _ in range(T):
	N = int(input())
	G = [[] for _ in range(N)]
	for _ in range(N - 1):
		(u, v) = map(int, input().split())
		(u, v) = (u, v)
		G[u].append(v)
		G[v].append(u)
	visited = [False] * N

	def dfs(n):
		visited[n] = True
		(r, l1, l2) = (0, 0, 0)
		for adj in G[n]:
			if visited[adj]:
				continue
			(r1, l) = dfs(adj)
			r += r1
			if l == 1:
				l1 += 1
			if l == 2:
				l2 += 1
		if l2 == 0:
			if l1 == 0:
				return (r, 1)
			else:
				return (r, 2)
		elif l2 % 2 == 0:
			return (r + l2 // 2, 0)
		else:
			return (r + l2 // 2, 2)
	(r, l) = dfs(0)
	if l == 2:
		r += 1
	print(r)


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import math
import os
import random
import re
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import math
import os
import random
import re
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	nust = int(input().strip())
	graph = dict(((i, []) for i in range(0, nust)))
	for j in range(nust - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
tape = int(input().strip())
for tt in range(tape):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()


import os
import sys
import collections
import queue

def solve():
	n = int(input().strip())
	graph = dict(((i, []) for i in range(0, n)))
	for j in range(n - 1):
		(x, y) = [int(p) for p in input().strip().split()]
		graph[x].append(y)
		graph[y].append(x)
	level = 1
	root = 0
	q = queue.Queue()
	q.put((root, level, None))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), leaf=None)
		for child in graph[item]:
			if child not in seen:
				q.put((child, level + 1, item))
				seen.add(child)
				tree[item]['children'].add(child)
	clusters = 1
	has_items_in_cluster = False
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			tree_item = tree[item]
			if not tree_item['children']:
				tree_item['leaf'] = True
			else:
				has_items_in_cluster = True
				branches = 0
				for child in tree_item['children']:
					if not tree[child]['leaf']:
						branches += 1
				if branches >= 2:
					new_clusters = branches // 2
					clusters += new_clusters
					if branches % 2 == 0:
						has_items_in_cluster = False
						parent = tree_item['parent']
						if parent is not None:
							tree[parent]['children'].remove(item)
	if not has_items_in_cluster:
		clusters -= 1
	print(clusters)
t = int(input().strip())
for tt in range(t):
	solve()