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>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
#define DBG(a) cerr<< "line "<<__LINE__ <<" : "<< #a <<" --> "<<(a)<<endl
#define eps 1e-8
#define eq(x,y) (fabs((x)-(y)) < eps)
using namespace std;
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int>pii;
int mod = 1e9+7;
long double pi = acosl(-1);
const ll infl = 1e17+100;
const int inf = 1e9+100;
const int nmax = 1e5+5;
const int MAXLG = log2(nmax)+1;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//typedef tree< ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ost;

int compo[nmax];
int L[nmax], R[nmax];
vector<int>g[nmax];
vector<int>g2[nmax];
int color[nmax];
int parent[nmax];

int findpar(int u){
    if(u == parent[u]) return u;
    return parent[u] = findpar(parent[u]);
}

struct Edge {
    int u, v;
    LL cap, flow;
    Edge() {}
    Edge(int u, int v, LL cap): u(u), v(v), cap(cap), flow(0) {}
};

struct Dinic {
    int N;
    vector<Edge> edges;
    vector<vector<int>> adj;
    vector<int> d, pt;

    Dinic(int N): N(N), edges(0), adj(N), d(N), pt(N) {}

    void AddEdge(int u, int v, LL cap) {
        if (u != v) {
            edges.emplace_back(u, v, cap);
            adj[u].emplace_back(edges.size() - 1);
            edges.emplace_back(v, u, 0);
            adj[v].emplace_back(edges.size() - 1);
        }
    }

    bool BFS(int S, int T) {
        queue<int> q({S});
        fill(d.begin(), d.end(), N + 1);
        d[S] = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            if (u == T) break;
            for (int k: adj[u]) {
                Edge &e = edges[k];
                if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
                    d[e.v] = d[e.u] + 1;
                    q.emplace(e.v);
                }
            }
        }
        return d[T] != N + 1;
    }

    LL DFS(int u, int T, LL flow = -1) {
        if (u == T || flow == 0) return flow;
        for (int &i = pt[u]; i < adj[u].size(); ++i) {
            Edge &e = edges[adj[u][i]];
            Edge &oe = edges[adj[u][i]^1];
            if (d[e.v] == d[e.u] + 1) {
                LL amt = e.cap - e.flow;
                if (flow != -1 && amt > flow) amt = flow;
                if (LL pushed = DFS(e.v, T, amt)) {
                    e.flow += pushed;
                    oe.flow -= pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }

    LL MaxFlow(int S, int T) {
        LL total = 0;
        while (BFS(S, T)) {
            fill(pt.begin(), pt.end(), 0);
            while (LL flow = DFS(S, T))
                total += flow;
        }
        return total;
    }
};

void dfs2(int u, int c, int p=0){
    compo[u] = c;
    if(g2[u].size()==0) L[c] = R[c] = u;
    for(int v : g2[u]) if(v!=p){
        dfs2(v, c, u);
    }
    if(g2[u].size()==1){
        if(p==0) L[c] = u;
        else R[c] = u;
    }
}

void dfs(int u, int p, int level){
    color[u] = level%2;
    for(int v : g[u]) if(v!=p){
        dfs(v, u, level+1);
    }
}

void solv(){
    int n;
    cin>>n;
    vector<pii>ejes;
    for(int i=1; i<n; i++){
        int u,v;
        cin>>u>>v;
        ejes.push_back({u,v});
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0, 0);
    Dinic flo(n+2);
    for(pii z : ejes){
        int u = z.first, v = z.second;
        if(color[u]){
            flo.AddEdge(v, u, 1);
        }
        else{
            flo.AddEdge(u, v, 1);
        }
    }
    for(int i=1; i<=n; i++) if(!color[i]) {
        flo.AddEdge(0, i, 2);
    }
    for(int i=1; i<=n; i++) if(color[i]) {
        flo.AddEdge(i, n+1, 2);
    }
    flo.MaxFlow(0, n+1);

    int cur = 0;
    for(pii z : ejes){
        int u = z.first, v = z.second;
        if(flo.edges[cur].flow){
            g2[v].push_back(u);
            g2[u].push_back(v);
//            cout<<u<<" - "<<v<<endl;
        }
        cur+=2;
    }
    int curcomp=0;
    for(int i=1; i<=n; i++){
        if(g2[i].size()<=1 and !compo[i]){
            dfs2(i, ++curcomp);
        }
    }
    for(int i=1; i<=curcomp; i++) parent[i] = i;

    vector<int>ans;
    for(pii z : ejes){
        int u = z.first, v = z.second;
        if(compo[u]!=compo[v]){
            int c1 = findpar(compo[u]);
            int c2 = findpar(compo[v]);
            parent[c1] = c2;

            ans.push_back(u), ans.push_back(v);
            ans.push_back(R[c1]), ans.push_back(L[c2]);

            L[c2] = L[c1];
        }
    }

    for(int i=1; i<=n; i++){
        g[i].clear(), g2[i].clear();
        parent[i]=color[i]=L[i]=R[i]=compo[i] = 0;
    }

    cout<<ans.size()/4<<"\n";
    for(int i=0; i<ans.size(); i++){
        cout<<ans[i]<<" ";
        if(i%4==3) cout<<"\n";
    }

    ans.clear();
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


    int tc;
    cin>>tc;
    while(tc--){
        solv();
    }
}
/*

*/