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;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll,ll>pll;

const int mod = 1e9 + 7;
const int N = 1e5 + 5;

template <class T>
T pow(T a, T b) {
    T res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

ll powmod(ll a, ll b, ll m){
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

bool isDeleted[N];
bool dp[N];
bool used[N];

void dfs(int cur, int parent, vector<vector<pii>>& graph){
    int childdegree = graph[cur].size();
    if(parent != -1){
        childdegree--;
    }
    for(auto vi : graph[cur]){
        if(vi.first == parent){
            continue;
        }
        dfs(vi.first, cur, graph);
        if(dp[vi.first] == true){
//            cout << "remove " << cur << " to " << vi.first << endl;
            childdegree--;
            isDeleted[vi.second] = true;
        }
    }
    if(childdegree == 2){
        dp[cur] = true;
    }
    if(childdegree > 2){
        dp[cur] = true;
        for(auto vi : graph[cur]){
            if(vi.first == parent){
                continue;
            }
            if(childdegree == 2){
                break;
            }
            if(dp[vi.first] == false){
//                cout << "remove " << cur << " to " << vi.first << endl;
                childdegree--;
                isDeleted[vi.second] = true;
            }
        }
    }
}

vector<int>leaves;

void dfs2(int cur, int root, vector<vector<pii>>& graph){
    used[cur] = true;
    int child = 0;
    for(auto vi : graph[cur]){
        if(isDeleted[vi.second] || used[vi.first]){
            continue;
        }
        dfs2(vi.first, root, graph);
        child++;
    }
    if(child == 0){
//        cout << "leaves at leaves " << cur << endl;
        leaves.push_back(cur);
    }
    if(cur == root && child == 1){
//        cout << "leaves here at root" << cur << endl;
        leaves.push_back(cur);
    }
}

void solve(int tc){
    int n;
    cin >> n;
    memset(isDeleted, false, sizeof(isDeleted));
    memset(dp, false, sizeof(dp));
    memset(used, false, sizeof(used));
    vector<vector<pii>>graph(n);
    for(int i = 0; i < n-1; i++){
        int s, d;
        cin >> s >> d;
        s--;
        d--;
//        cout << s << " and " << d << endl;
        graph[s].pb(mp(d, i));
        graph[d].pb(mp(s, i));
    }
    // make all nodes have degree 2
    dfs(0, -1, graph);

    vector<pii>bamboos;

    // find leaves in each component
    for(int i = 0; i < n; i++){
        if(used[i] == false){
//            cout << "doing " << i << endl;
            dfs2(i, i, graph);
            if ((int)leaves.size() == 2) {
                bamboos.push_back({leaves[0], leaves[1]});
            }
            if ((int)leaves.size() == 1) {
                bamboos.push_back({leaves.back(), leaves.back()});
            }
            leaves.clear();
        }
        // careful here
    }

    vector<pii>added;
    for(int i = 1; i < bamboos.size(); i++){
        added.pb(mp(bamboos[i].first, bamboos[i-1].second));
    }

    vector<pii>deleted;
    for(int i = 0; i < n; i++){
        for(auto vi : graph[i]){
            if(isDeleted[vi.second] && i < vi.first){
                deleted.pb(mp(i, vi.first));
            }
        }
    }

//    cout << added.size() << " vs " << deleted.size() << endl;
    vector<vector<int>>ans;
//    assert(deleted.size() == added.size());
    for(int i = 0; i < added.size(); i++){
        vector<int>cur;
        cur.pb(deleted[i].first);
        cur.pb(deleted[i].second);
        cur.pb(added[i].first);
        cur.pb(added[i].second);
        ans.pb(cur);
    }
    cout << ans.size() << endl;
    for(auto vi : ans){
        for(auto j : vi){
            cout << j + 1 << " ";
        }
        cout << endl;
    }

}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	for(int i = 1; i <= t; i++){
		solve(i);
	}
	return 0;
}