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 fi first
#define se second
#define ll long long
#define dl double long

using namespace std;

const int N = 2e5 + 7;
const long long mod = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
int a[N];
int c[N];
bool used[N];
vector<int> v[N],id;
map<pair<int, int>, int> f;

void dfs(int x)
{
    used[x] = true;
    int cnt = 0;
    for(auto y : v[x]){
        if(f.find({x, y}) == f.end()){
            cnt++;
        }
        if(used[y])continue;
        if(f.find({x, y}) == f.end()){
            dfs(y);
        }
    }
    if(cnt <= 1)id.push_back(x);
}

void solve()
{
    cin >> n;
    for(int i = 1; i < n; i++){
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if((int)v[i].size() == 1){
            q.push(i);
        }
        a[i] = (int)v[i].size();
        c[i] = max(0, a[i] - 2);
    }
    map<pair<int, int>, int> ff;
    vector<pair<int, int>> del;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto y : v[x]){
            a[y]--;
            if(a[y] == 1){
                q.push(y);
            }
            if(ff.find({x, y}) != ff.end())continue;
            if(c[x] > 0 && c[y] > 0){
                c[x]--, c[y]--;
                ff[{x, y}] = 1;
                ff[{y, x}] = 1;
                del.push_back({x, y});
            }
        }
        for(auto y : v[x]){
            if(ff.find({x, y}) != ff.end())continue;
            if(c[x] > 0){
                c[x]--;
                ff[{x, y}] = 1;
                ff[{y, x}] = 1;
                del.push_back({x, y});
            }
        }
    }
    for(auto &x : del){
        assert(f.find({x.fi, x.se}) == f.end());
        f[{x.fi, x.se}] = f[{x.se, x.fi}] = 1;
    }
    vector<pair<int, int>> add;
    for(int i = 1, ls = -1; i <= n; i++){
        if(!used[i]){
            dfs(i);
            assert(!id.empty());
            if(ls != -1)add.push_back({ls, id[0]});
            ls = id.back();
            id.clear();
        }
    }
    //assert((int)del.size() == (int)add.size());
    cout << (int)del.size() << "\n";
    for(int i = 0; i < (int)del.size(); i++){
        cout << del[i].fi << " " << del[i].se << " " << add[i].fi << " " << add[i].se << "\n";
    }
    for(int i = 1; i <= n; i++){
        a[i] = c[i] = 0;
        v[i].clear();
        used[i] = false;
    }
    del.clear();
    add.clear();
    f.clear();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int T = 1;
    cin >> T;
    while( T-- ){
        solve();
    }
}