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;

template<class Xs>
int sz(const Xs &xs) { return static_cast<int>(xs.size()); }

using i64 = int64_t;
using f80 = long double;

using Str = string;
template<class T = int> using Vec = vector<T>;
template<class K = int, class H = hash<K>> using US = unordered_set<K, H>;
template<class K, class V, class H = hash<K>> using UM = unordered_map<K, V, H>;

template<class U = int, class V = U> using P = pair<U, V>;
using G = Vec<Vec<int>>;

struct Solver {
    Solver(G g) : g(g) { n= g.size();}

    Vec<P<P<int>>> getAns() {
        edges[0].resize(n);
        edges[1].resize(n);
        dp[0].resize(n);
        dp[1].resize(n);
        dfs(0);
        dfs2(0);
        sort(left.begin(), left.end());
        Vec<int> degree(n);
        for (int i = 0; i < n; ++i) degree[i] = g[i].size();
        vector<P<int>> deleted;
        Vec<P<int>> added;
        for (int i = 0; i < n; ++i) for (int j : g[i])
            {
                if (i < j)
                {
                    if (!binary_search(left.begin(), left.end(), P<int>{i, j}))
                    {
                        deleted.emplace_back(i, j);
                        degree[i]--;
                        degree[j]--;
                    }
                }
            }

        g.assign(n, Vec<int>());
        visited.assign(n, false);
        for (auto [x, y] : left)
        {
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for (int i = 0; i < n; ++i)
        {
            if (!visited[i]) {
                comps.push_back(Vec<int>());
                comp(i);
            }
        }
        for (int i = 0; i + 1 < comps.size();++i)
        {
            int v = 0;
            int u;
            for (int x : comps[i]) if (degree[x] <= 1) {
                    v = x;
                    degree[v]++;
                    break;
                }
            for (int x : comps[i + 1]) if (degree[x] <= 1) {
                    u = x;
                    degree[u]++;
                    break;
                }
            added.emplace_back(u, v);
        }
        Vec<P<P<int>>> res;
        for (int i = 0; i < deleted.size(); ++i)
            res.emplace_back(deleted[i], added[i]);
        return res;
    }

    void comp(int v)
    {
        visited[v] = true;
        comps.back().push_back(v);
        for (int u : g[v]) if (!visited[u]) comp(u);
    }

    void dfs(int vert, int par = -1)
    {
        Vec<P<int>> lose_if_edge;
        i64 res = 0;
        for (int nxt: g[vert])
        {
            if (nxt != par)
            {
                dfs(nxt, vert);
                lose_if_edge.emplace_back(dp[0][nxt] - dp[1][nxt], nxt);
                res += dp[0][nxt];
            }
        }
        sort(lose_if_edge.begin(), lose_if_edge.end());
        int num = 0;
        while (num < min<int>(2, lose_if_edge.size()) && lose_if_edge[num].first == 0)
        {
            ++num;
        }
        for (int i = 0; i< num;++i)
        {
            edges[0][vert].push_back(lose_if_edge[i].second);
        }
        dp[0][vert] = res + num;
        if (num >= 1)
        {
            edges[1][vert].push_back(lose_if_edge[0].second);
        }
        dp[1][vert] = res + min(num, 1);
    }

    void dfs2(int vert, int par=-1, int i=0)
    {
        for (auto nxt : edges[i][vert])
        {
            if (nxt < vert)
            {
                left.emplace_back(nxt, vert);
            }
            else
                left.emplace_back(vert, nxt);
        }
        for (int nxt : g[vert])
        {
            if (nxt == par) continue;
            bool used = false;
            for (int in : edges[i][vert])
            {
                if (nxt == in) used = true;
            }
            dfs2(nxt, vert, (used ? 1 : 0));
        }
    }
    Vec<bool> visited;
    Vec<Vec<int>> comps;
    Vec<P<int>> left;
    G g;
    array<Vec<int>, 2> dp;
    int n;
    array<G, 2> edges;
};

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i)
    {
        int n; cin >> n;
        G g(n);
        for (int j = 0; j < n - 1; ++j)
        {
            int a, b;
            cin >> a >> b;--a;--b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        auto ans = Solver(g).getAns();
        cout << ans.size() << '\n';
        for (auto [x, y]: ans)
        {
            cout << x.first + 1 << ' ' << x.second + 1 << ' ' << y.first  + 1 << ' ' << y.second + 1 << '\n';
        }
    }
}

namespace {
    auto fast_io = [] {
#ifndef DEBUG
#  ifndef INTERACTIVE
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
#  endif // INTERACTIVE
#  ifdef FILES
        freopen(FILES".in", "r", stdin);
        freopen(FILES".out", "w", stdout);
#  endif // FILES
#endif // DEBUG
        cout << setprecision(8) << fixed;
        cerr << boolalpha << setprecision(4) << fixed;

        return 0;
    }();
} // namespace