Nastia has an unweighted tree with n vertices and wants to play with it!

The girl will perform the following operation with her tree, as long as she needs:

  1. Remove any existing edge. 
  2. Add an edge between any pair of vertices. 



What is the minimum number of operations Nastia needs to get a bamboo from a tree? A bamboo is a tree in which no node has a degree greater than 2.

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

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

Next n - 1 lines of each test cases describe the edges of the tree in form a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i).

It's guaranteed the given graph is a tree and the sum of n in one test doesn't exceed 2 ⋅ 10^5.

Output

For each test case in the first line print a single integer k — the minimum number of operations required to obtain a bamboo from the initial tree.

In the next k lines print 4 integers x_1, y_1, x_2, y_2 (1 ≤ x_1, y_1, x_2, y_{2} ≤ n, x_1 ≠ y_1, x_2 ≠ y_2) — this way you remove the edge (x_1, y_1) and add an undirected edge (x_2, y_2).

Note that the edge (x_1, y_1) must be present in the graph at the moment of removing.

Example

Input


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


Output


2
2 5 6 7
3 6 4 5
0

Note

Note the graph can be unconnected after a certain operation.

Consider the first test case of the example: 

<image> The red edges are removed, and the green ones are added.

Difficulty: VERY_HARD
Tags: Graph traversal

Constructive algorithms

Implementation

Greedy algorithms

Tree algorithms

Dynamic programming

Spanning trees

Data structures
Skill types: Dynamic programming

Data structures

Greedy algorithms

Starter code:

Solutions:
def dfs(x, e, v, g):
	v[x] = True
	c = 0
	for y in e[x]:
		if not y in v:
			if dfs(y, e, v, g):
				c += 1
				if c > 2:
					g.append((x, y))
			else:
				g.append((x, y))
	if c < 2:
		return True
	if x != 1:
		return False

def leaf(x, e):
	p = 0
	while True:
		u = 0
		for y in e[x]:
			if y != p:
				u = y
				break
		if u == 0:
			break
		p = x
		x = u
	return x

def solve(n, e):
	g = []
	dfs(1, e, {}, g)
	for (x, y) in g:
		e[x].remove(y)
		e[y].remove(x)
	z = []
	l = leaf(1, e)
	for (p, y) in g:
		r = leaf(y, e)
		z.append((p, y, l, r))
		l = leaf(r, e)
	print(len(z))
	if len(z) > 0:
		print('\n'.join(map(lambda x: ' '.join(map(str, x)), z)))

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		e = {}
		for i in range(n - 1):
			(a, b) = map(int, input().split())
			if not a in e:
				e[a] = []
			if not b in e:
				e[b] = []
			e[a].append(b)
			e[b].append(a)
		solve(n, e)
import threading
import sys
sys.setrecursionlimit(10 ** 5 + 1)
threading.stack_size(262000)
main = threading.Thread(target=main)
main.start()
main.join()


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

class FastIO(IOBase):
	newlines = 0

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

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

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

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

class IOWrapper(IOBase):

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

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

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

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

class UF:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n
		self.size = AI(n, 1)
		self.edge = A(n)

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			self.edge[pu] += 1
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			self.edge[pu] += self.edge[pv] + 1
			self.size[pu] += self.size[pv]
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv
			self.edge[pv] += self.edge[pu] + 1
			self.size[pv] += self.size[pu]

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = AI(n, inf)
	d[s] = 0
	heap = [(0, s)]
	vis = A(n)
	while heap:
		(dis, u) = heappop(heap)
		if vis[u]:
			continue
		vis[u] = 1
		for (v, w) in graph[u]:
			if d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
from heapq import *

@bootstrap
def dfs(r, p):
	s = 0
	one = []
	for ch in g[r]:
		if ch != p:
			child[r].append(ch)
			yield dfs(ch, r)
			ma = max(dp[ch])
			s += ma
			t1 = dp[ch][1]
			if t1 + 1 > ma:
				heappush(one, [ma - t1 - 1, ch])
	if not one:
		dp[r] = [s, s, s]
	elif len(one) == 1:
		(v, ch) = heappop(one)
		ma = max(dp[ch])
		for i in range(3):
			if dp[ch][i] == ma:
				break
		g1[r].append((ch, i))
		dp[r] = [s, s - v, s - v]
	else:
		(v, ch) = heappop(one)
		(v2, ch2) = heappop(one)
		ma = max(dp[ch])
		for i in range(3):
			if dp[ch][i] == ma:
				break
		g1[r].append((ch, i))
		g2[r].append((ch, i))
		ma2 = max(dp[ch2])
		for i in range(3):
			if dp[ch2][i] == ma2:
				break
		g2[r].append((ch2, i))
		dp[r] = [s, s - v, s - v - v2]
	yield None

@bootstrap
def dfs2(r, t):
	used = set()
	if t == 1:
		(ch, i) = g1[r][0]
		used.add(ch)
		(x, y) = (r, ch)
		if x > y:
			(x, y) = (y, x)
		nedge.add((x, y))
		yield dfs2(ch, i)
	elif t == 2:
		for (ch, i) in g2[r]:
			used.add(ch)
			(x, y) = (r, ch)
			if x > y:
				(x, y) = (y, x)
			nedge.add((x, y))
			yield dfs2(ch, i)
	for ch in child[r]:
		if ch not in used:
			ma = max(dp[ch])
			for i in range(3):
				if dp[ch][i] == ma:
					break
			yield dfs2(ch, i)
	yield None
t = N()
for i in range(t):
	n = N()
	g = G(n)
	edge = []
	for i in range(n - 1):
		(a, b) = RL()
		a -= 1
		b -= 1
		g[a].append(b)
		g[b].append(a)
		if a > b:
			(a, b) = (b, a)
		edge.append((a, b))
	g1 = G(n)
	g2 = G(n)
	dp = [[0] * 3 for i in range(n)]
	child = G(n)
	dfs(0, -1)
	ma = max(dp[0])
	for i in range(3):
		if dp[0][i] == ma:
			break
	nedge = set()
	dfs2(0, i)
	delt = []
	add = []
	for (x, y) in edge:
		if (x, y) not in nedge:
			delt.append((x, y))
	na = G(n)
	for (x, y) in nedge:
		na[x].append(y)
		na[y].append(x)
	vis = A(n)
	for i in range(n):
		if len(na[i]) == 0:
			add.append((i, i))
		elif len(na[i]) == 1 and (not vis[i]):
			u = i
			vis[u] = 1
			v = na[u][0]
			while len(na[v]) != 1:
				for ch in na[v]:
					if ch != i:
						(i, v) = (v, ch)
						break
			add.append((u, v))
			vis[v] = 1
	i = 0
	print(len(delt))
	for i in range(len(delt)):
		(x2, y2) = (add[i][1], add[i + 1][0])
		(x1, y1) = delt[i]
		print(x1 + 1, y1 + 1, x2 + 1, y2 + 1)


import time
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

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

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

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

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

class IOWrapper(IOBase):

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

def getInt():
	return int(input())

def getStrs():
	return input().split()

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

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def bootstrap(f, stack=[]):

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

def solve():
	N = getInt()
	G = [[] for _ in range(N)]
	deg = [0] * N
	par = [-1] * N
	for i in range(N - 1):
		(a, b) = getInts()
		G[a - 1].append(b - 1)
		G[b - 1].append(a - 1)
	to_add = []
	leaves = []
	removed = set()
	global count
	count = 0

	@bootstrap
	def dfs(node):
		global count
		children = 0
		for neigh in G[node]:
			if neigh != par[node]:
				par[neigh] = node
				yield dfs(neigh)
				if (node, neigh) not in removed:
					children += 1
		if children == 2:
			if par[node] != -1:
				count += 1
				removed.add((par[node], node))
		if children > 2:
			if par[node] != -1:
				count += 1
				removed.add((par[node], node))
			idx = len(G[node]) - 1
			while children > 2:
				if G[node][idx] == par[node]:
					idx -= 1
				count += 1
				while (node, G[node][idx]) in removed or G[node][idx] == par[node]:
					idx -= 1
				removed.add((node, G[node][idx]))
				children -= 1
				idx -= 1
		yield
	dfs(0)
	ends = []
	used = [0] * N
	global flag

	@bootstrap
	def dfs2(node):
		global flag
		if flag:
			neighs = 1
		else:
			neighs = 0
		flag = True
		used[node] = 1
		for neigh in G[node]:
			if not used[neigh] and (node, neigh) not in removed and ((neigh, node) not in removed):
				neighs += 1
				yield dfs2(neigh)
		if neighs == 1:
			ends.append(node)
		elif neighs == 0:
			ends.append(node)
			ends.append(node)
		yield
	for i in range(N):
		flag = False
		if not used[i]:
			dfs2(i)
	removed = list(removed)
	print(len(removed))
	j = 0
	for i in range(1, len(ends) - 1, 2):
		print(removed[j][0] + 1, removed[j][1] + 1, ends[i] + 1, ends[i + 1] + 1)
		j += 1
	return
for _ in range(getInt()):
	solve()


def leaf(f, u):
	if len(m[u]) == 1:
		return u
	else:
		for v in m[u]:
			if v != f:
				ans = leaf(u, v)
				if ans:
					return ans

def cut():
	stack = []
	stack.append([0, -1, leaf(-1, 0)])
	while len(stack):
		(a, *b) = stack.pop()
		(f, u) = b
		if a == 0:
			stack.append([1, f, u])
			for v in m[u] - {f}:
				stack.append([0, u, v])
		elif a == 1:
			du = len(m[u])
			it = iter(m[u] - {f})
			if du >= 3:
				while du >= 4:
					v = next(it)
					ct.append((u + 1, v + 1))
					m[v].remove(u)
					m[u].remove(v)
					du -= 1
				if f != -1:
					ct.append((f + 1, u + 1))
					m[u].remove(f)
					m[f].remove(u)

def link():
	l = set()
	node = -1
	for i in range(n):
		if len(m[i]) <= 1:
			l.add(i)
	v = next(iter(l))
	l.discard(v)
	u = end(v)
	l.discard(u)
	while len(l) != 0:
		v = next(iter(l))
		l.discard(v)
		lk.append((u + 1, v + 1))
		u = end(v)
		l.discard(u)

def end(s):
	if len(m[s]) == 0:
		return s
	f = s
	s = next(iter(m[s]))
	while len(m[s]) != 1:
		(f, s) = (s, next(iter(m[s] - {f})))
	return s
for test in range(int(input())):
	n = int(input())
	m = [set() for i in range(n)]
	ct = []
	lk = []
	for i in range(n - 1):
		(a, b) = (int(i) - 1 for i in input().split())
		m[a].add(b)
		m[b].add(a)
	cut()
	link()
	op = zip(ct, lk)
	print(len(ct))
	for (c, l) in op:
		print(*c, *l)


from sys import stdin, stdout
input = stdin.readline
from types import GeneratorType

def bootstrap(f, stack=[]):

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

@bootstrap
def detach(start, parent):
	global removed
	childs = list(graph[start])
	for i in childs:
		if i == parent:
			continue
		yield detach(i, start)
	childs = graph[start].copy()
	if parent:
		childs.remove(parent)
	childs = list(childs)
	if len(childs) >= 2:
		if parent:
			removed.append((start, parent))
			graph[start].remove(parent)
			graph[parent].remove(start)
		for i in childs[2:]:
			removed.append((start, i))
			graph[start].remove(i)
			graph[i].remove(start)
	yield

@bootstrap
def dfs(start):
	global check
	vis.add(start)
	count = 0
	for i in graph[start]:
		count += 1
		if i not in vis:
			yield dfs(i)
	if count == 0:
		leaves.append(start)
		leaves.append(start)
	elif count == 1:
		leaves.append(start)
	yield
t = int(input())
for _ in range(t):
	n = int(input())
	graph = [set() for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a].add(b)
		graph[b].add(a)
	removed = []
	added = []
	leaves = []
	detach(1, 0)
	vis = set()
	for i in range(1, n + 1):
		if i not in vis:
			dfs(i)
	for i in range(1, len(leaves) - 1, 2):
		added.append((leaves[i], leaves[i + 1]))
	x = len(removed)
	print(x)
	for i in range(x):
		stdout.write(str(removed[i][0]) + ' ' + str(removed[i][1]) + ' ' + str(added[i][0]) + ' ' + str(added[i][1]) + '\n')


import sys
sys.setrecursionlimit(250010)

def dfs(x):
	tag[x] = 1
	ql = -1
	tgs = (-1, -1)
	l = 0
	for v in lian[x]:
		if tag[v] == 0:
			t = dfs(v)
			gs[v][0] = t[0]
			gs[v][1] = t[1]
			if gs[v][0] == -1 and ql == -1:
				ql = v
			q[x].append(v)
			l += 1
	if l == 0:
		tag[x] = 0
		return (-1, x)
	if ql == -1:
		for i in range(l - 1):
			ans[0] += 1
			res[ans[0] - 1] = (q[x][i], x, gs[q[x][i]][0], gs[q[x][i + 1]][0])
			gs[q[x][i + 1]][0] = gs[q[x][i]][1]
		ans[0] += 1
		res[ans[0] - 1] = (q[x][l - 1], x, gs[q[x][l - 1]][0], x)
		tgs = (-1, gs[q[x][l - 1]][1])
	else:
		v2 = ql
		last = -1
		for i in range(l):
			if gs[q[x][i]][0] != -1:
				ans[0] += 1
				res[ans[0] - 1] = (q[x][i], x, gs[q[x][i]][0], gs[v2][1])
				gs[v2][1] = gs[q[x][i]][1]
			else:
				last = q[x][i]
		for i in range(l):
			if gs[q[x][i]][0] == -1 and q[x][i] != v2 and (q[x][i] != last):
				ans[0] += 1
				res[ans[0] - 1] = (q[x][i], x, q[x][i], gs[v2][1])
				gs[v2][1] = gs[q[x][i]][1]
		if last == v2:
			tgs = (-1, gs[v2][1])
		else:
			tgs = (gs[v2][1], gs[last][1])
	tag[x] = 0
	return tgs
for _ in range(int(input())):
	n = int(input())
	q = [[] for i in range(n + 1)]
	lian = [[] for i in range(n + 1)]
	tag = [0] * (n + 1)
	res = [0] * (n + 1)
	ans = [0]
	gs = [[-1, -1] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		lian[a].append(b)
		lian[b].append(a)
	dfs(1)
	print(ans[0])
	for t in range(ans[0]):
		i = res[t]
		print(i[0], i[1], i[2], i[3])


import sys
sys.setrecursionlimit(111111)

def dfs(x):
	tag[x] = 1
	q = []
	ql = -1
	tgs = [-1, -1]
	for v in lian[x]:
		if tag[v] == 0:
			gs[v] = dfs(v)
			if gs[v][0] == -1 and ql == -1:
				ql = v
			q.append(v)
	if len(q) == 0:
		return [-1, x]
	if ql == -1:
		for i in range(len(q) - 1):
			v1 = q[i]
			v2 = q[i + 1]
			ans[0] += 1
			res.append((v1, x, gs[v1][0], gs[v2][0]))
			gs[v2][0] = gs[v1][1]
		v = q[len(q) - 1]
		ans[0] += 1
		res.append((v, x, gs[v][0], x))
		tgs = [-1, gs[v][1]]
	else:
		v2 = ql
		last = -1
		for i in range(len(q)):
			v1 = q[i]
			if gs[v1][0] != -1:
				ans[0] += 1
				res.append((v1, x, gs[v1][0], gs[v2][1]))
				gs[v2][1] = gs[v1][1]
			else:
				last = v1
		for i in range(len(q)):
			v1 = q[i]
			if gs[v1][0] == -1 and v1 != v2 and (v1 != last):
				ans[0] += 1
				res.append((v1, x, v1, gs[v2][1]))
				gs[v2][1] = gs[v1][1]
		if last == v2:
			tgs = [-1, gs[v2][1]]
		else:
			tgs = [gs[v2][1], gs[last][1]]
	return tgs
	for i in range(len(q) - 1):
		v = q[i][1]
		dus = q[i][0]
		if dus == 3:
			ans[0] += 1
for _ in range(int(input())):
	n = int(input())
	du = [0] * (n + 1)
	lian = [[] for i in range(n + 1)]
	tag = [0] * (n + 1)
	res = []
	ans = [0]
	gs = [[-1, -1] for i in range(n + 1)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		du[a] += 1
		du[b] += 1
		lian[a].append(b)
		lian[b].append(a)
	dfs(1)
	print(ans[0])
	for i in res:
		print(i[0], i[1], i[2], i[3])


import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
	n = int(input())
	edges = [list(map(int, input().split())) for i in range(n - 1)]
	adj = [set() for i in range(n + 1)]
	for (a, b) in edges:
		adj[a].add(b)
		adj[b].add(a)
	operations = []
	visited = [0] * (n + 1)
	parent = [0] * (n + 1)
	s = [1]
	while s:
		c = s[-1]
		if not visited[c]:
			visited[c] = 1
			for ne in adj[c]:
				if not visited[ne]:
					parent[ne] = c
					s.append(ne)
		else:
			if len(adj[c]) > 2:
				if parent[c]:
					operations.append([c, parent[c]])
					adj[parent[c]].remove(c)
					adj[c].remove(parent[c])
				while len(adj[c]) > 2:
					x = adj[c].pop()
					adj[x].remove(c)
					operations.append([x, c])
			s.pop()
	endpoints = []
	visited = [0] * (n + 1)
	for i in range(1, n + 1):
		if not visited[i]:
			endpoints.append([])
			s = [i]
			while s:
				c = s[-1]
				if not visited[c]:
					visited[c] = 1
					if len(adj[c]) <= 1:
						endpoints[-1].append(c)
					for ne in adj[c]:
						s.append(ne)
				else:
					s.pop()
	assert len(operations) == len(endpoints) - 1
	for i in range(len(endpoints) - 1):
		if len(endpoints[i]) == 1:
			endpoints[i].append(endpoints[i][0])
		operations[i].extend([endpoints[i][1], endpoints[i + 1][0]])
	print(len(operations))
	for operation in operations:
		print(*operation)


import sys

def readline():
	return map(int, input().split())

def solve():
	n = int(input())
	nbrs = [list() for __ in range(n)]
	for __ in range(n - 1):
		(ai, bi) = readline()
		ai -= 1
		bi -= 1
		nbrs[ai].append(bi)
		nbrs[bi].append(ai)
	to_delete = list()
	pos = 0
	parent = -1
	arr = list(nbrs[pos])
	stack = [(pos, parent, arr)]
	while stack:
		(pos, parent, arr) = stack[-1]
		if arr:
			child = arr.pop()
			if child != parent and len(nbrs[child]) > 1:
				(pos, parent) = (child, pos)
				stack.append((pos, parent, list(nbrs[pos])))
				continue
		else:
			stack.pop()
			if len(nbrs[pos]) > 2 and parent >= 0:
				nbrs[pos].remove(parent)
				nbrs[parent].remove(pos)
				to_delete.append((pos, parent))
			while len(nbrs[pos]) > 2:
				child = nbrs[pos].pop()
				nbrs[child].remove(pos)
				to_delete.append((pos, child))
	segments = list()
	is_tail = [False] * n
	for i in range(n):
		p = len(nbrs[i])
		assert p <= 2
		if p == 0:
			segments.append((i, i))
		if is_tail[i] or p != 1:
			continue
		(pos,) = nbrs[i]
		prev = i
		while len(nbrs[pos]) == 2:
			(prev, pos) = (pos, sum(nbrs[pos]) - prev)
		assert len(nbrs[pos]) == 1
		is_tail[pos] = True
		segments.append((i, pos))
	(a, b) = segments.pop()
	k = len(to_delete)
	assert k == len(segments)
	print(k)
	for ((x1, y1), (c, d)) in zip(to_delete, segments):
		print(x1 + 1, y1 + 1, b + 1, d + 1)
		b = c

def main():
	t = int(input())
	for __ in range(t):
		solve()
main()


from math import sqrt

def sol():
	n = int(input())
	G = []
	for i in range(n):
		G.append(set())
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		G[a].add(b)
		G[b].add(a)
	newG = []
	for elem in G:
		newG.append(elem.copy())
	visited = [0] * n
	stack = [(0, 0)]
	to_del = []
	while len(stack) > 0:
		(cur, parent) = stack[-1]
		if visited[cur] == 0:
			visited[cur] = 1
			for elem in G[cur]:
				if elem != parent:
					stack.append((elem, cur))
		else:
			stack.pop()
			visited[cur] = 2
			if parent != cur and len(newG[cur]) > 2 and (len(newG[parent]) > 2):
				newG[cur].remove(parent)
				newG[parent].remove(cur)
				to_del.append((cur, parent))
	for i in range(n):
		while len(newG[i]) > 2:
			AA = newG[i].pop()
			newG[AA].remove(i)
			to_del.append((i, AA))
	hang = set()
	for (i, elem) in enumerate(newG):
		if len(elem) <= 1:
			hang.add(i)
	pairs = []
	while len(hang) > 0:
		A = hang.pop()
		AA = A
		while len(newG[A]) > 0:
			B = newG[A].pop()
			newG[B].remove(A)
			A = B
		if A in hang:
			hang.remove(A)
		pairs.append((AA, A, hang))
	print(len(to_del))
	for i in range(len(to_del)):
		print(to_del[i][0] + 1, to_del[i][1] + 1, pairs[i][1] + 1, pairs[i + 1][0] + 1)
for iter in range(int(input())):
	sol()


def order(n, G):
	ans = []
	parent = [-1] * n

	def dfs(x, par):
		parent[x] = par
		for y in G[x]:
			if y == par:
				continue
			dfs(y, x)
		ans.append(x)
	dfs(1, -1)
	return (ans, parent)

def solve(n, G, topo, parent):
	to_remove = []
	for x in topo:
		p = parent[x]
		num_child = len(G[x]) - (1 if p in G[x] else 0)
		if num_child <= 1:
			pass
		else:
			if p != -1:
				to_remove.append((x, p))
				G[x].remove(p)
				G[p].remove(x)
			to_select = 0
			tmp = []
			for y in G[x]:
				if y == p:
					continue
				if to_select < 2:
					to_select += 1
				else:
					to_remove.append((y, x))
					tmp.append(y)
			for y in tmp:
				G[x].remove(y)
				G[y].remove(x)
	visited = [False] * n

	def find_bamboo(x):
		visited[x] = True
		if not G[x]:
			return (x, x)
		par = x
		while len(G[x]) > 1:
			for y in G[x]:
				if y != par:
					par = x
					x = y
					break
		par = x
		cur = list(G[x])[0]
		visited[x] = True
		visited[cur] = True
		while len(G[cur]) > 1:
			for y in G[cur]:
				if y != par:
					par = cur
					cur = y
					visited[y] = True
					break
		return (x, cur)
	bamboos = []
	for x in range(n):
		if not visited[x]:
			(u, v) = find_bamboo(x)
			bamboos.append((u, v))
	k = len(to_remove)
	print(k)
	for i in range(k):
		(a, b) = (bamboos[i][1], bamboos[i + 1][0])
		(u, v) = to_remove[i]
		print(u + 1, v + 1, a + 1, b + 1)
	return
for nt in range(int(input())):
	n = int(input())
	G = [set() for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		G[a - 1].add(b - 1)
		G[b - 1].add(a - 1)
	(topo, parent) = order(n, G)
	solve(n, G, topo, parent)


import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
INF = 10 ** 17

def test(n):
	p = [i + 1 for i in range(n)]
	random.shuffle(p)
	Edge = []
	for i in range(1, n):
		pv = random.randint(0, i - 1)
		Edge.append((p[pv], p[i]))
	return Edge

def line(N):
	node = [i + 2 for i in range(N - 1)]
	random.shuffle(node)
	node = [1] + node
	edge = []
	for i in range(1, N):
		edge.append((node[i - 1], node[i]))
	return edge

def star(N):
	node = [i + 1 for i in range(N)]
	random.shuffle(node)
	edge = []
	for i in range(1, N):
		if random.randint(0, 9999) % 2:
			edge.append((node[0], node[i]))
		else:
			edge.append((node[i], node[0]))
	return edge
for _ in range(int(input())):
	n = int(input())
	edge = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = mi()
		edge[a - 1].append(b - 1)
		edge[b - 1].append(a - 1)
	deq = deque([0])
	parent = [-1] * n
	topo = []
	while deq:
		v = deq.popleft()
		topo.append(v)
		for nv in edge[v]:
			if nv != parent[v]:
				parent[nv] = v
				deq.append(nv)
	topo = topo[::-1]
	dp = [[0, INF, INF] for v in range(n)]
	not_cut = [[None, -1, (-1, -1)] for v in range(n)]

	def merge(v, nv):
		(a, b, c) = dp[v]
		dp[v][0] += min(dp[nv]) + 1
		dp[v][1] += min(dp[nv]) + 1
		dp[v][2] += min(dp[nv]) + 1
		if b + min(dp[nv][0], dp[nv][1]) < dp[v][2]:
			not_cut[v][2] = (not_cut[v][1], nv)
			dp[v][2] = b + min(dp[nv][0], dp[nv][1])
		if a + min(dp[nv][0], dp[nv][1]) < dp[v][1]:
			not_cut[v][1] = nv
			dp[v][1] = a + min(dp[nv][0], dp[nv][1])
	for v in topo:
		for nv in edge[v]:
			if nv != parent[v]:
				merge(v, nv)
	topo = topo[::-1]
	limit = [2 for v in range(n)]
	print(min(dp[0]))
	CUT = []
	_ADD = []
	for v in topo:
		if limit[v] == 1:
			if dp[v][1] < dp[v][0]:
				for nv in edge[v]:
					if nv != parent[v]:
						if nv != not_cut[v][1]:
							CUT.append((v, nv))
						else:
							limit[nv] = 1
			else:
				for nv in edge[v]:
					if nv != parent[v]:
						CUT.append((v, nv))
		elif dp[v][2] < dp[v][1]:
			(a, b) = (-1, -1)
			for nv in edge[v]:
				if nv != parent[v]:
					if nv not in not_cut[v][2]:
						CUT.append((v, nv))
					else:
						limit[nv] = 1
						while not_cut[nv][1] != -1:
							if dp[nv][1] < dp[nv][0]:
								nv = not_cut[nv][1]
							else:
								break
						if a == -1:
							a = nv
						else:
							b = nv
			_ADD.append((a, b))
		elif dp[v][1] < dp[v][0]:
			(a, b) = (v, -1)
			for nv in edge[v]:
				if nv != parent[v]:
					if nv != not_cut[v][1]:
						CUT.append((v, nv))
					else:
						limit[nv] = 1
						while not_cut[nv][1] != -1:
							if dp[nv][1] < dp[nv][0]:
								nv = not_cut[nv][1]
							else:
								break
						b = nv
			_ADD.append((a, b))
		else:
			_ADD.append((v, v))
			for nv in edge[v]:
				if nv != parent[v]:
					CUT.append((v, nv))
	for i in range(len(_ADD) - 1):
		(a, b) = _ADD[i]
		(c, d) = _ADD[i + 1]
		(u, v) = CUT[i]
		print(u + 1, v + 1, b + 1, c + 1)
	assert len(CUT) == min(dp[0])
	assert len(CUT) == len(_ADD) - 1


import io
import os
from collections import defaultdict
from types import GeneratorType
from heapq import heappush, heappop

def bootstrap(f, stack=[]):

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

def solve(N, edges):
	graph = [[] for i in range(N)]
	for (u, v) in edges:
		graph[u].append(v)
		graph[v].append(u)
	dp1 = [0] * N
	dp2 = [0] * N
	bp1 = [()] * N
	bp2 = [()] * N

	@bootstrap
	def dfs(node, p):
		for child in graph[node]:
			if child != p:
				yield dfs(child, node)
		total = 0
		heap = []
		for child in graph[node]:
			if child != p:
				total += dp2[child]
				heappush(heap, (dp2[child] - dp1[child], child))
		if heap:
			(gain1, child1) = heappop(heap)
			gain1 *= -1
			score1 = 1 + total + gain1
			if dp1[node] < score1:
				dp1[node] = score1
				bp1[node] = (child1,)
			if dp2[node] < score1:
				dp2[node] = score1
				bp2[node] = (child1,)
			if heap:
				(gain2, child2) = heappop(heap)
				gain2 *= -1
				assert gain2 <= gain1
				score2 = 2 + total + gain1 + gain2
				if dp2[node] < score2:
					dp2[node] = score2
					bp2[node] = (child1, child2)
		assert dp1[node] <= dp2[node]
		yield
	dfs(0, -1)
	disconnect = []

	@bootstrap
	def dfs2(node, p, isConnected):
		if not isConnected and dp1[node] < dp2[node]:
			connectedChild = bp2[node]
		else:
			connectedChild = bp1[node]
		for child in graph[node]:
			if child != p:
				childConnected = child in connectedChild
				if not childConnected:
					disconnect.append((node, child))
				yield dfs2(child, node, childConnected)
		yield
	dfs2(0, -1, False)
	disconnect = set(disconnect)
	uf = UnionFind(N)
	degree = [0] * N
	for (u, v) in edges:
		if (u, v) in disconnect or (v, u) in disconnect:
			continue
		degree[u] += 1
		degree[v] += 1
		uf.union(u, v)
	paths = defaultdict(list)
	for u in range(N):
		if degree[u] <= 1:
			paths[uf.find(u)].append(u)
	endpoints = list(paths.values())
	ops = []
	for i in range(len(endpoints) - 1):
		x = endpoints[i][-1]
		y = endpoints[i + 1][0]
		(u, v) = disconnect.pop()
		ops.append(' '.join((str(i + 1) for i in [u, v, x, y])))
	assert not disconnect
	assert len(ops) == N - 1 - max(dp1[0], dp2[0])
	return str(len(ops)) + '\n' + '\n'.join(ops)

class UnionFind:

	def __init__(self, N):
		self.p = [-1 for i in range(N)]

	def find(self, i):
		if self.p[i] >= 0:
			self.p[i] = self.find(self.p[i])
			return self.p[i]
		else:
			return i

	def union(self, i, j):
		root1 = self.find(j)
		root2 = self.find(i)
		if root1 == root2:
			return
		size1 = -self.p[root1]
		size2 = -self.p[root2]
		if size1 < size2:
			self.p[root1] = root2
			self.p[root2] = -(size1 + size2)
		else:
			self.p[root2] = root1
			self.p[root1] = -(size1 + size2)

	def getComponentSize(self, i):
		return -self.p[self.find(i)]
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	edges = [[int(x) - 1 for x in input().split()] for i in range(N - 1)]
	ans = solve(N, edges)
	print(ans)