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:
#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
template<class T1,class T2,class T3>T1 ksm(T1 a,T2 b,T3 mod){T1 ans=1;while(b){if(b&1)ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
#ifndef ONLINE_JUDGE
template<class T>T __gcd(T a,T b){ll r;while(b>0){r=a%b;a=b;b=r;}return a;}
#endif
#define inf INT_MAX
#define Max(x,y) x=max(x,y)
#define Min(x,y) x=min(x,y)
#define Out(t) printf("%s\n",(t)?"YES":"NO")
const double pi=acos(-1.);
const int def=100010;
const int mod=1000000007;
using namespace std;

vector<int>mp[def];
int fa[def],in[def],pos[def],tp[def];
bool delfa[def];
vector<pair<int,int>>del,add;

int find(int x)
{
	return tp[x]==x?x:tp[x]=find(tp[x]);
}

void merge(int x,int y)
{
	x=find(x);y=find(y);
	tp[x]=y;
}

void build(int now)
{
	in[now]=mp[now].size();
	for(auto i:mp[now])
		if(i!=fa[now]){
			fa[i]=now;
			build(i);
		}
}

void dfs(int now)
{
	for(auto i:mp[now])
		if(i!=fa[now])
			dfs(i);
	if(in[fa[now]]>2&&in[now]>2){
		del.push_back({now,fa[now]});
		in[fa[now]]--;
		in[now]--;
		delfa[now]=true;
	}
	if(in[now]<=2){
		for(auto i:mp[now])
			if(i!=fa[now]&&!delfa[i])
				merge(now,i);
		return;
	}
	for(auto i:mp[now])if(i!=fa[now]){
		if(in[now]<=2)break;
		if(delfa[i])continue;
		del.push_back({now,i});
		delfa[i]=true;
		in[now]--;
		in[i]--;
	}
	for(auto i:mp[now])
		if(i!=fa[now]&&!delfa[i])
			merge(now,i);
}

int main()
{	int _=1,__=1,n,x,y;
	for(((1)?scanf("%d",&_):EOF);_;_--,__++){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			delfa[i]=false;
			mp[i].clear();
			tp[i]=i;
		}
		del.clear();
		add.clear();
		for(int i=1;i<n;i++){
			scanf("%d %d",&x,&y);
			mp[x].push_back(y);
			mp[y].push_back(x);
		}
		fa[1]=0;
		build(1);
		dfs(1);
		for(int i=1;i<=n;i++)pos[i]=i;
		sort(pos+1,pos+n+1,[&](int x,int y){
			return in[x]<in[y];
		});
		for(int i=n;i>=1;i--)if(!in[pos[i]]){
			add.push_back({pos[i],pos[i+1]});
			merge(pos[i],pos[i+1]);
			in[pos[i]]++;
			in[pos[i+1]]++;
		}
		sort(pos+1,pos+n+1,[&](int x,int y){
			return in[x]<in[y];
		});
		for(int i=1;i<n;i++)if(in[pos[i]]<2){
			int j=i+1;
			while(j<=n&&(in[pos[j]]>=2||find(pos[i])==find(pos[j])))j++;
			if(j>n)continue;
			merge(pos[i],pos[j]);
			in[pos[i]]++;
			in[pos[j]]++;
			add.push_back({pos[i],pos[j]});
		}
		printf("%lu\n",del.size());
		for(int i=0;i<del.size();i++)
			printf("%d %d %d %d\n",del[i].first,del[i].second,add[i].first,add[i].second);
	}
	return 0;
}