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 = 100000 + 9;

vector<int> G[N];

int dp[N][3];

bool cmp(int u, int v) {
    return min(dp[u][0], dp[u][1]) - min(min(dp[u][0], dp[u][1]), dp[u][2])
           < min(dp[v][0], dp[v][1]) - min(min(dp[v][0], dp[v][1]), dp[v][2]);
}

void dfs(int u, int p) {
    for (auto it = G[u].begin(); it != G[u].end(); ++it) {
        if (*it == p) { G[u].erase(it); break; }
    }
    for (int v : G[u]) dfs(v, u);
    sort(G[u].begin(), G[u].end(), cmp);
    dp[u][0] = G[u].size();
    for (int v : G[u]) {
        dp[u][0] += min(min(dp[v][0], dp[v][1]), dp[v][2]);
    }
    if ((int)G[u].size() >= 1) {
        int v = G[u][0];
        dp[u][1] = dp[u][0] - 1 + min(dp[v][0], dp[v][1]) - min(min(dp[v][0], dp[v][1]), dp[v][2]);
    }
    else {
        dp[u][1] = N;
    }
    if ((int)G[u].size() >= 2) {
        int v = G[u][0], v2 = G[u][1];
        dp[u][2] = dp[u][0] - 2 + min(dp[v][0], dp[v][1]) - min(min(dp[v][0], dp[v][1]), dp[v][2])
                   + min(dp[v2][0], dp[v2][1]) - min(min(dp[v2][0], dp[v2][1]), dp[v2][2]);
    }
    else {
        dp[u][2] = N;
    }
}

vector<pair<int, int>> del, add;

void dfs2(int u, int p) {
    if (p) {
        int minv = min(dp[u][0], dp[u][1]);
        if (minv == dp[u][0]) {
            while ((int)G[u].size() > 0) {
                int v = G[u].back();
                G[u].pop_back();
                dfs2(v, 0);
                del.push_back({u, v});
            }
        }
        else {
            while ((int)G[u].size() > 1) {
                int v = G[u].back();
                G[u].pop_back();
                dfs2(v, 0);
                del.push_back({u, v});
            }
            dfs2(G[u][0], u);
        }
        G[u].push_back(p);
    }
    else {
        int minv = min(min(dp[u][0], dp[u][1]), dp[u][2]);
        if (minv == dp[u][0]) {
            while ((int)G[u].size() > 0) {
                int v = G[u].back();
                G[u].pop_back();
                dfs2(v, 0);
                del.push_back({u, v});
            }
        }
        else if (minv == dp[u][1]) {
            while ((int)G[u].size() > 1) {
                int v = G[u].back();
                G[u].pop_back();
                dfs2(v, 0);
                del.push_back({u, v});
            }
            dfs2(G[u][0], u);
        }
        else {
            while ((int)G[u].size() > 2) {
                int v = G[u].back();
                G[u].pop_back();
                dfs2(v, 0);
                del.push_back({u, v});
            }
            dfs2(G[u][0], u);
            dfs2(G[u][1], u);
        }
    }
}

bool vis[N];

vector<int> tmp;

void dfs3(int u, int p) {
    vis[u] = true;
    if ((int)G[u].size() == 0) {
        tmp.push_back(u);
        tmp.push_back(u);
    }
    else if ((int)G[u].size() == 1) {
        tmp.push_back(u);
    }
    for (int v : G[u]) if (v != p) dfs3(v, u);
}

void solve() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        G[i].clear();
    }
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    del.clear();
    add.clear();
    dfs2(1, 0);
    memset(vis, 0, (n + 5) * sizeof(*vis));
    tmp.clear();
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) dfs3(i, 0);
    }
    for (int i = 1, sz = tmp.size(); i < sz - 1; i += 2) {
        add.push_back({tmp[i], tmp[i + 1]});
    }
    printf("%d\n", (int)del.size());
    for (int i = 0, sz = del.size(); i < sz; ++i) {
        printf("%d %d %d %d\n", del[i].first, del[i].second, add[i].first, add[i].second);
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}