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>
using namespace std;
const int N=1e5+5;
int tot;
int head[N],to[N*2],next1[N*2];
void lian(int x,int y)
{
    to[++tot]=y;
    next1[tot]=head[x];
    head[x]=tot;
}
int d[N],k;
struct qw{
    int a,b,c,d;
}e[N];
struct er{
    int a,b;
}jie[N];
void dfs(int x,int fa)
{
    jie[x].a=x,jie[x].b=0;
    for(int i=head[x];i;i=next1[i])
    {
        int v=to[i];
        if(v==fa) continue;
        d[x]++;
        dfs(v,x);
    }
    if(d[x]==0) return;
    int v1=-1;
    for(int i=head[x];i;i=next1[i])
    {
        int v=to[i];
        if(v==fa) continue;
        if(jie[v].b==0)
        {
            if(v1==-1) jie[x].a=jie[v].a;
            else if(jie[x].b==0) jie[x].b=jie[v].a;
            else e[++k]=(qw){v,x,v,jie[x].a},jie[x].a=jie[v].a;
            v1=0;
            
        }
    }
    if(v1==-1)
    {
        for(int i=head[x];i;i=next1[i])
        {
            int v=to[i];
            if(v==fa) continue;
            v1=v;
            e[++k]=(qw){v,x,x,jie[v].a};
            jie[x].a=jie[v].b;
            break;
        }
    }
    for(int i=head[x];i;i=next1[i])
    {
        int v=to[i];
        if(v==fa||jie[v].b==0||v==v1) continue;
        if(jie[v].a&&jie[v].b) e[++k]=(qw){v,x,jie[v].a,jie[x].a},jie[x].a=jie[v].b;
        else e[++k]=(qw){v,x,jie[x].a,v},jie[x].a=jie[v].a;
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        int x,y;
        for(int i=1;i<=n-1;i++)
        {
            scanf("%d %d",&x,&y);
            lian(x,y),lian(y,x);
        }
        k=0;
        dfs(1,0);
        printf("%d\n",k);
        for(int i=1;i<=k;i++)
        printf("%d %d %d %d\n",e[i].a,e[i].b,e[i].c,e[i].d);
        tot=0;
        for(int i=1;i<=n;i++) head[i]=d[i]=0;
    }
    return 0;
}