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 = 100005;

set<int> graph[N];
int parent[N];
int visited[N];
vector<pair<int, int>> dels;
vector<pair<int, int>> adds;

void setupp(int v, int p){
    parent[v] = p;
    for(auto x : graph[v]){
        if(x != p)
            setupp(x, v);
    }
}

void setup(int v){
    set<int> st = graph[v];
    for(auto u : st){
        if(u != parent[v])
            setup(u);
    }

    int children = 0;
    for(auto x : graph[v]){
        if(x != parent[v])
            children++;
    }

    if(children <= 1){
        return;
    }
    if(children == 2 && parent[v] != -1){
        graph[v].erase(parent[v]);
        graph[parent[v]].erase(v);
        dels.push_back({parent[v], v});
        parent[v] = -1;
        return;
    }

    if(parent[v] != -1){
        graph[v].erase(parent[v]);
        graph[parent[v]].erase(v);
        dels.push_back({parent[v], v});
        parent[v] = -1;
    }

    int fr = -1, sc = -1;
    st = graph[v];
    for(auto u : st){
        if(fr == -1){
            fr = u;
            continue;
        }
        if(sc == -1){
            sc = u;
            continue;
        }
        graph[v].erase(u);
        graph[u].erase(v);
        parent[u] = -1;
        dels.push_back({u, v});
    }
}

set<int> leafs;

void solve(int v, int p){
    int c = 0;
    for(auto x : graph[v]){
        if(x != p){
            c++;
        }
    }

    if(c == 0 || p == -1)
        leafs.erase(v);

    if(!leafs.empty() && c == 0){
        int nxt = *leafs.begin();
        graph[v].insert(nxt);
        graph[nxt].insert(v);
        adds.push_back({nxt, v});
        leafs.erase(leafs.begin());
    }

    for(auto x : graph[v]){
        if(x != p)
            solve(x, v);
    }
}

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

    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; ++i){
            graph[i].clear();
            parent[i] = -1;

        }
        adds.clear();
        dels.clear();
        leafs.clear();

        for(int i = 0; i < n - 1; ++i){
            int x, y;
            cin >> x >> y;
            graph[x].insert(y);
            graph[y].insert(x);
        }

        setupp(1, -1);
        setup(1);

        int fr = -1;
        for(int i = 1; i <= n; ++i){
            if(graph[i].size() == 1 || graph[i].size() == 0){
                leafs.insert(i);
                fr = i;
            }
        }

        solve(fr, -1);

        if(adds.size() == 0 && 0 != dels.size()){
            while(1);
        }

        cout << max((int)adds.size(), (int)dels.size()) << "\n";
        for(int i = 0; i < max((int)adds.size(), (int)dels.size()); ++i){
            cout << dels[i].first << " " << dels[i].second << " " << adds[i].first << " " << adds[i].second << "\n";
        }
    }
    return 0;
}