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 fs first
#define se second
#define y0 qwertyuiop
#define y1 asdfghjkl

#ifdef imeimi
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...)
#endif

using namespace std;
typedef long long ll;
typedef long double lf;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<lf, lf> pff;

int n;
vector<int> edge[100005];
int dp[100005][2];
vector<int> con[100005][2];
void dfs1(int x, int p) {
    vector<pii> c;
    int sum = 0;
    for (int i : edge[x]) {
        if (i == p) continue;
        dfs1(i, x);
        sum += dp[i][0] + 1;
        c.emplace_back(dp[i][1] - dp[i][0], i);
    }
    sort(c.begin(), c.end());
    dp[x][0] = dp[x][1] = sum;
    if (int(c.size()) > 0) {
        dp[x][0] += c[0].first - 1;
        con[x][0].push_back(c[0].second);
        dp[x][1] += c[0].first - 1;
        con[x][1].push_back(c[0].second);
    }
    if (int(c.size()) > 1) {
        dp[x][0] += c[1].first - 1;
        con[x][0].push_back(c[1].second);
    }
}

int ord;
vector<int> G[100005];
vector<pair<pii, pii>> E;
int dfs2(int x, int p, int c = 0, int o = 0) {
    if (!o) o = ++ord;
    int deg = c;
    for (int i : edge[x]) {
        if (i == p) continue;
        bool in = 0;
        for (int j : con[x][c]) if (i == j) in = 1;
        deg += in;
        int r = dfs2(i, x, in, in ? o : 0);
        if (!in) E.emplace_back(pii(i, x), pii(r, o));
    }
    while (deg++ < 2) G[o].push_back(x);
    return o;
}

int par[100005];
int find(int x) {
    if (par[x]) return par[x] = find(par[x]);
    return x;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        edge[i].clear(), G[i].clear(), par[i] = 0;
        con[i][0].clear();
        con[i][1].clear();
    }
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs1(1, 0);
    printf("%d\n", dp[1][0]);
    ord = 0;
    E.clear();
    dfs2(1, 0);
    for (auto [e1, e2] : E) {
        e2.first = find(e2.first);
        e2.second = find(e2.second);
        printf("%d %d %d %d\n", e1.first, e1.second, G[e2.first][0], G[e2.second][1]);
        G[e2.first][0] = G[e2.second][0];
        par[e2.second] = e2.first;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.precision(30); cout << fixed;
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}