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 <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> e[200005];
vector<int> pick[200005];
int pre[200005];
int dp[200005][2];

void dfs(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
    // dp[i][0] root i is not on side
    // dp[i][1] root i is one of the side
    vector<pair<int, int> > tmp;
    int sum = 0;
    for (auto v : e[u]) {
        if (v == fa) continue;
        sum += dp[v][0] + 1;
        tmp.emplace_back(make_pair(-dp[v][0] - 1 + dp[v][1], v));
    }
    sort(tmp.begin(), tmp.end());
    if (tmp.size() == 0) {
        dp[u][0] = 0;
        dp[u][1] = 0;
    } else if (tmp.size() == 1) {
        dp[u][0] = dp[u][1] = min(sum, sum + tmp[0].first);
        if (tmp[0].first < 0) pre[u] = tmp[0].second;
        else pre[u] = -1;
    } else {
        dp[u][1] = min(sum, sum + tmp[0].first);
        if (tmp[0].first < 0) pre[u] = tmp[0].second;
        else pre[u] = -1;
        dp[u][0] = sum + tmp[0].first + tmp[1].first;
        pick[u].emplace_back(tmp[0].second);
        pick[u].emplace_back(tmp[1].second);
    }
    //cout << u << " " << dp[u][0] << " " << dp[u][1] << endl;
}

pair<int, int> find_ans(int u, int state, int fa) {
    int sz = 0;
    for (auto v : e[u]) {
        if (v == fa) continue;
        sz++;
    }
    pair<int, int> pa = make_pair(u, u);
    if (sz == 1) {
        int node = pre[u];
        if (node != -1) {
            for (auto v : e[u]) {
                if (v == fa) continue;
                if (v == node) {
                    pa = find_ans(v, 1, u);
                    if (pa.first == v) pa.first = u;
                    else pa.second = u;
                }
            }
        } else {
            for (auto v : e[u]) {
                if (v == fa) continue;
                if (v == node) continue;
                else {
                    pair<int, int> new_pa = find_ans(v, 0, u);
                    printf("%d %d %d %d\n", u, v, pa.first, new_pa.first);
                    pa = make_pair(pa.second, new_pa.second);
                }

            }
        }
    } else if (sz > 1) {
        if (state == 1) {
            int node = pre[u];
            for (auto v : e[u]) {
                if (v == fa) continue;
                if (v == node) {
                    pa = find_ans(v, 1, u);
                    if (pa.second == v) pa.second = u;
                    else pa.first = u;
                    if (pa.second != u) swap(pa.first, pa.second);
                }
            }
            for (auto v : e[u]) {
                if (v == fa) continue;
                if (v == node) continue;
                pair<int, int> new_pa = find_ans(v, 0, u);
                printf("%d %d %d %d\n", u, v, pa.first, new_pa.first);
                pa = make_pair(pa.second, new_pa.second);
                if (pa.second != u) swap(pa.first, pa.second);
            }
        } else {
            for (auto v : e[u]) {
                if (v == fa) continue;
                if (v == pick[u][0] || v == pick[u][1]) {
                    pair<int, int> pa1 = find_ans(v, 1, u);
                    int node = pa1.first;
                    if (pa1.first == v) node = pa1.second;
                    if (pa.first == u) pa.first = node;
                    else pa.second = node;
                }
            }
            for (auto v : e[u]) {
                if (v == fa) continue;
                if (v == pick[u][0] || v == pick[u][1]) continue;
                pair<int, int> new_pa = find_ans(v, 0, u);
                printf("%d %d %d %d\n", u, v, pa.first, new_pa.first);
                pa = make_pair(pa.second, new_pa.second);
            }
        }
    }
    //cout << u << " " << state << " " << pa.first << " " << pa.second << endl;
    return pa;
}

int main(void) {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 1;i <= n;i++) {
            e[i].clear();
            pick[i].clear();
        }
        for (int i = 0;i < n - 1;i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            e[u].emplace_back(v);
            e[v].emplace_back(u);
        }
        dfs(1, -1);
        printf("%d\n", min(dp[1][0], dp[1][1]));
        if (dp[1][0] > dp[1][1]) find_ans(1, 1, -1);
        else find_ans(1, 0, -1);
    }
    return 0;
}