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>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

const int MAXN=1e5+10;
vector<int> g[MAXN];
int dp[MAXN][2];

int solve(int pos, int up, int p){
	int &r=dp[pos][up];
	if(r>=0)return r;
	r=1e9;
	
	vector<ii> v;
	int totno=0;
	for(auto x:g[pos]) if(x!=p){
		int is=solve(x,1,pos), no=solve(x,0,pos);
		totno+=no;
		v.pb({no-is,x});
	}
	sort(ALL(v)); reverse(ALL(v));
	
	//alguien de arriba
	if(up){
		r=totno;
		//lo extiendo
		if(SZ(v)) r=min(r,totno-v[0].fst);
	}
	
	else{
		//cuantos matcheo para abajo
		fore(i,0,3) if(i<=SZ(v)){
			int now=1+totno;
			fore(j,0,i) now-=v[j].fst;
			r=min(r,now);
		}
	}
	
	return r;
}

vector<int> pt[MAXN],ex[MAXN];
int idd,in[MAXN],par[MAXN],cs[MAXN];

void paint(int pos, int up, int p, int wh){
	pt[wh].pb(pos); cs[pos]=wh;
	
	vector<ii> v;
	int totno=0;
	for(auto x:g[pos]) if(x!=p){
		int is=solve(x,1,pos), no=solve(x,0,pos);
		totno+=no;
		v.pb({no-is,x});
	}
	sort(ALL(v)); reverse(ALL(v));
	
	set<int> to;
	if(up&&solve(pos,up,p)!=totno) to.insert(v[0].snd);
	if(!up){
		int bst=1e9,am=-1;
		fore(i,0,3) if(i<=SZ(v)){
			int now=1+totno;
			fore(j,0,i) now-=v[j].fst;
			if(now<bst) bst=now,am=i;
		}
		fore(i,0,am) to.insert(v[i].snd);
	}
	
	for(auto x:g[pos]) if(x!=p){
		if(to.count(x)) paint(x,1,pos,wh);
		else paint(x,0,pos,++idd);
	}
}

void dfs(int pos, int p=-1){
	in[pos]=idd++; par[pos]=p;
	for(auto x:g[pos]) if(x!=p) dfs(x,pos);
}

bool cmp(int x, int y){return in[x]<in[y];}



int main(){FIN;
	int tt; cin>>tt;
	while(tt--){
		int n; cin>>n;
		//clean
		fore(i,0,n) dp[i][0]=dp[i][1]=-1;
		fore(i,0,n) g[i].clear(),pt[i].clear(),ex[i].clear();
		
		fore(i,1,n){
			int x,y; cin>>x>>y; x--; y--;
			g[x].pb(y); g[y].pb(x);
		}
		
		int wh=0;
		fore(i,1,n) if(SZ(g[i])>1)wh=i;
		
		idd=0;
		dfs(wh);
		idd=0;
		paint(wh,0,-1,0);

		fore(i,0,idd+1){
			sort(ALL(pt[i]),cmp);
			for(auto x:pt[i]){
				int is=1,tot=0;
				for(auto y:g[x]) if(y!=par[x]&&cs[y]==cs[x]) is=0,tot++;
				if(x==pt[i][0]&&tot==1)is=1;
				if(is) ex[i].pb(x);
			}
		}
		
		fore(i,0,idd+1){
			//cout<<"\npath: ";for(auto x:pt[i])cout<<x+1<<" ";cout<<"\n";
			//cout<<"extremos: "; for(auto x:ex[i])cout<<x+1<<" ";cout<<"\n";
		}
		
		
		int pre=ex[0][0];
		cout<<idd<<endl;
		fore(i,1,idd+1){
			cout<<pt[i][0]+1<<" "<<par[pt[i][0]]+1<<" "<<ex[i][0]+1<<" "<<pre+1<<endl;
			pre=ex[i].back();
		}
	}
}