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:
/*
 * @Author: your name
 * @Date: 2021-05-08 19:41:57
 * @LastEditTime: 2021-05-08 20:27:43
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \code_formal\codeforces\cf edu108-\720_4.cpp
 */
#include <bits/stdc++.h>
#define pr printf
#define sc scanf
#define for0(i, n) for (i = 0; i < n; i++)
#define for1n(i, n) for (i = 1; i <= n; i++)
#define forab(i, a, b) for (i = a; i <= b; i++)
#define forba(i, a, b) for (i = b; i >= a; i--)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<vector<int>>
#define vt2 vector<tuple<int, int>>
#define vt3 vector<tuple<int, int, int>>
#define mem(ara, n) memset(ara, n, sizeof(ara))
#define memb(ara) memset(ara, false, sizeof(ara))
#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define sz(x) x.size()
const int N = 2e5 + 100;
const int mod = 1e9 + 7;
namespace often
{
    inline void input(int &res)
    {
        char c = getchar();
        res = 0;
        int f = 1;
        while (!isdigit(c))
        {
            f ^= c == '-';
            c = getchar();
        }
        while (isdigit(c))
        {
            res = (res << 3) + (res << 1) + (c ^ 48);
            c = getchar();
        }
        res = f ? res : -res;
    }
    inline int qpow(int a, int b)
    {
        int ans = 1, base = a;
        while (b)
        {
            if (b & 1)
                ans = (ans * base % mod + mod) % mod;
            base = (base * base % mod + mod) % mod;
            b >>= 1;
        }
        return ans;
    }
    int fact(int n)
    {
        int res = 1;
        for (int i = 1; i <= n; i++)
            res = res * 1ll * i % mod;
        return res;
    }
    int C(int n, int k)
    {
        return fact(n) * 1ll * qpow(fact(k), mod - 2) % mod * 1ll * qpow(fact(n - k), mod - 2) % mod;
    }
    int exgcd(int a, int b, int &x, int &y)
    {
        if (b == 0)
        {
            x = 1, y = 0;
            return a;
        }
        int res = exgcd(b, a % b, x, y);
        int t = y;
        y = x - (a / b) * y;
        x = t;
        return res;
    }
    int invmod(int a, int mod)
    {
        int x, y;
        exgcd(a, mod, x, y);
        x %= mod;
        if (x < 0)
            x += mod;
        return x;
    }
}
using namespace often;
using namespace std;

signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int _ = 1;
    cin >> _;
    while (_--)
    {
        int n;
        cin >> n;
        vector<vector<int>> g(n+1);
        for (int i = 1; i < n; i++)
        {
            int u, v;
            cin >> u >> v;
            g[u].emplace_back(v);
            g[v].emplace_back(u);
        }
        vector<tuple<int, int>>  add;
        vector<tuple<int, int>>  remove;
        function<tuple<int, int>(int, int)> dfs = [&](int u, int p) {
            tuple<int, int> cur = make_tuple(u, u);
            vector<tuple<int, int>>  vec;
            for (auto v : g[u])
            {
                if (v != p)
                {
                    auto x = dfs(v, u);
                    if (get<1>(x) == v && get<1>(cur) == u)
                    {
                        (get<0>(cur) == u ? get<0>(cur) : get<1>(cur)) = get<0>(x);
                    }
                    else
                    {
                        vec.emplace_back(x);
                        remove.emplace_back(u, v);
                    }
                }
            }
            for (auto x : vec)
            {
                add.emplace_back(get<0>(cur), get<1>(x));
                get<0>(cur) = get<0>(x);
            }
            return cur;
        };
        dfs(1, -1);
        cout << (int)sz(add) << endl;
        for (int i = 0; i < (int)sz(add); i++)
        {
            int x0, y0, x1, y1;
            tie(x0, y0) = remove[i];
            tie(x1, y1) = add[i];
            cout << x0 << " " << y0 << " " << x1 << " " << y1 << endl;
        }
    }

    return 0;
}