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,e) for(int i = 0; i < e; i++)
#define reps(i,s,e) for(ll i = s; i <= e; i++)
#define rev(i,s) for(ll i = s; ~i; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())
#define pb push_back
#define ff first
#define ss second

using namespace std;
typedef long long ll;
const ll MOD=1000000007;

int n;
vector<set<int>> adj;
vector<pair<int, int>> broken, joined;
vector<bool> visited;

inline void brk(int u, int v){
    adj[u].erase(v);
    adj[v].erase(u);

    broken.pb({u+1, v+1});
}

void dfs1(int u, int par){
    auto it = adj[u].begin();
    while(it != adj[u].end()) {
        if(*it == par) it++;
        else dfs1(*it++, u);
    }

    if(sz(adj[u]) > 2 and u != par) brk(u, par);

    int cnt = 2;
    it = adj[u].begin();
    while(it != adj[u].end()){
        if(cnt) {cnt--; it++; continue;}
        else brk(*it++, u);  
    }
}

void dfs2(int u, vector<int>& ans){
    visited[u] = true;
    for(auto it : adj[u])
        if(!visited[it]) dfs2(it, ans);

    if(sz(adj[u]) == 1) ans.pb(u);
    if(sz(adj[u]) == 0) {ans.pb(u); ans.pb(u);}
}

void solve(){
    cin >> n;
    adj = vector<set<int>>(n);
    broken.clear(); joined.clear();

    rep(i, n-1){
        int u, v;
        cin >> u >> v;
        u--; v--;

        adj[u].insert(v);
        adj[v].insert(u);
    }

    dfs1(0, 0);

    visited = vector<bool>(n, false);
    int end = -1;
    rep(i, n){
        if(!visited[i]){
            vector<int> ends;
            dfs2(i, ends);

            if(end != -1) joined.pb({end+1, ends[0]+1});
            end = ends[1];
            ends.clear();
        }
    }

    cout << sz(broken) << '\n';
    // cout << sz(joined) << '\n';
    rep(i, sz(broken)) cout << broken[i].ff << ' ' << broken[i].ss << ' ' << joined[i].ff << ' ' << joined[i].ss << '\n';
}

int main(){
#ifdef k4droid3
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while(t--)
        solve();
    
    return 0;
}