Problem: 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.

Solution (in CPP):

Solution:
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set> 
#include<iomanip>
#define IOS 	cin.tie(0), ios::sync_with_stdio(false) 
#define x first
#define y second

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e5 + 10, M = N * 2, mod = 3;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const double pi = acos(-1);
const int P = 131;

int n;
vector<pii> v1, v2;

int h[N], e[M], ne[M], idx;

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u, int fa)
{
	int l = 0, r = 0;
	for(int i = h[u] ; ~i ; i = ne[i])
	{
		int j = e[i];
		if(j == fa) continue;
		int cur = dfs(j, u);	//当前儿子所处的子树是否还有能连边的节点 
		if(!cur) continue;
		//如果已经有两个儿子，就直接把边切了 
		if(r) v1.push_back({u, j}), v2.push_back({j, cur});
		else if(!l) l = cur;
		else if(!r) r = cur;
	}
	
	//如果有父亲，两个儿子，就把和父亲的边切了，然后把两个儿子放进v2 
	if(l && r && fa)
		v1.push_back({fa, u}), v2.push_back({l, r});
		
	//	return l ? (r && fa) ? 0 : l : u;
	if(l)
	{
		if(r && fa) return 0;	//和父亲的边被切掉了 
		else return l;			//有左儿子返回左儿子 
	}
	return u;					//当前结点没有左右儿子了 
}

int main()
{
	IOS; 
	int T;
	cin >> T;
	while(T --)
	{
		cin >> n;
		idx = 0;
		for(int i = 1 ; i <= n ; i ++) h[i] = -1;
		for(int i = 1 ; i < n ; i ++)
		{
			int a, b;
			cin >> a >> b;
			add(a, b), add(b, a);
		}
			
		int m = dfs(1, 0);
		cout << v1.size() << "\n";
		for(int i = 0 ; i < v1.size() ; ++ i)
			cout << v1[i].x << " " << v1[i].y << " " << m << " " << v2[i].x << "\n", m = v2[i].y;
		v1.clear(), v2.clear();
	 } 

	return 0;
} 

/*
1
7
1 2
1 3
1 4
1 5
5 6
5 7
*/