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 rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

int t,n,wt[100010],cpl[100010],dp[100010][3],lst[100010][3];
bool ch[100010],vis[100010];
vector <int> g[100010],wtv[100010],cplv[100010],ng[100010];
vector <pii> del,add,prs;

/*
1. 全都cpl，另起炉灶wt
2. 一个wt，其它cpl，连接起来wt
3. 两个wt，其它cpl，连接起来cpl
*/
void dfs(int pos,int par)
{
  rep(i,g[pos].size()) if(g[pos][i]!=par) dfs(g[pos][i],pos);
  vector <int> son;son.clear();
  LL cpls=0;
  rep(i,g[pos].size()) if(g[pos][i]!=par)
  {
    son.pb(g[pos][i]);
    cpls+=cpl[g[pos][i]];
  }

  wt[pos]=cpls+1;//1
  rep(i,son.size()) if(wt[pos]>cpls-cpl[son[i]]+wt[son[i]])//2
  {
    wt[pos]=cpls-cpl[son[i]]+wt[son[i]];
    wtv[pos]={son[i]};
  }

  rep(i,son.size()+5) rep(j,3) dp[i][j]=1e9,lst[i][j]=0;
  dp[0][0]=0;
  rep(i,son.size()) rep(j,3) if(dp[i][j]!=1e9)//3
  {
    if(dp[i+1][j]>dp[i][j]+cpl[son[i]]) dp[i+1][j]=dp[i][j]+cpl[son[i]],lst[i+1][j]=0;
    if(j==0&&dp[i+1][1]>dp[i][j]+wt[son[i]]) dp[i+1][1]=dp[i][j]+wt[son[i]],lst[i+1][1]=1;
    if(j==1&&dp[i+1][2]>dp[i][j]+wt[son[i]]-1) dp[i+1][2]=dp[i][j]+wt[son[i]]-1,lst[i+1][2]=1;
  }
  cpl[pos]=dp[son.size()][2];
  int cur=2,ii=son.size();
  while(ii>0)
  {
    if(lst[ii][cur]==1) cplv[pos].pb(son[ii-1]);
    cur-=lst[ii][cur];--ii;
  }

  if(cpl[pos]>wt[pos])
  {
    cpl[pos]=wt[pos];
    ch[pos]=true;
  }
}

void getAns(int pos,int par,int ty)
{
  map <int,bool> mp;mp.clear();
  if(ty==0||(ty==1&&ch[pos])) rep(i,wtv[pos].size()) mp[wtv[pos][i]]=true;
  else rep(i,cplv[pos].size()) mp[cplv[pos][i]]=true;
  rep(i,g[pos].size()) if(g[pos][i]!=par)
  {
    if(mp[g[pos][i]])
    {
      ng[pos].pb(g[pos][i]);
      ng[g[pos][i]].pb(pos);
      getAns(g[pos][i],pos,0);
    }
    else
    {
      del.pb(mpr(pos,g[pos][i]));
      getAns(g[pos][i],pos,1);
    }
  }
}

int dfs2(int pos,int par)
{
  vis[pos]=true;
  rep(i,ng[pos].size()) if(ng[pos][i]!=par) return dfs2(ng[pos][i],pos);
  return pos;
}

void solve()
{
  scanf("%d",&n);
  rep(i,n+5) g[i].clear(),ng[i].clear(),wtv[i].clear(),cplv[i].clear(),ch[i]=false;
  int x,y;
  rep(i,n-1)
  {
    scanf("%d%d",&x,&y);
    g[x].pb(y);g[y].pb(x);
  }
  dfs(1,0);
  printf("%d\n",cpl[1]-1);
  del.clear();
  getAns(1,0,1);
  add.clear();prs.clear();
  rep(i,n+5) vis[i]=false;
  repn(i,n) if(!vis[i]&&ng[i].size()<=1) prs.pb(mpr(i,dfs2(i,0)));
  rep(i,prs.size()-1) add.pb(mpr(prs[i].se,prs[i+1].fi));
  rep(i,del.size()) printf("%d %d %d %d\n",del[i].fi,del[i].se,add[i].fi,add[i].se); 
}

int main()
{
  cin>>t;
  rep(tn,t) solve();
  return 0;
}