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:
//
// Created by zhujunchao on 2021/5/7.
//

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 2e5 + 7;
const int mod = 1e9 + 7;
int head, nh;
int d[N], hd[N], tl[N];
bool vis[N];
vector<pair<int, int> > ans1, ans2;
vector<vector<int> > e;
void dfs(int x, int fa, int r){
    for(int i = 0; i < e[x].size(); i++){
        if(e[x][i] == fa) continue;
        int v = e[x][i];
        dfs(v, x, 1);
        if(hd[v] == v){
            if(tl[x] == x){
                tl[x] = tl[v];
                vis[v] = 1;
            }
            else if(hd[x] == x){
                hd[x] = tl[v];
                vis[v] = 1;
            }
        }
    }
    for(int i = 0; i < e[x].size(); i++){
        if(e[x][i] == fa) continue;
        int v = e[x][i];
        if(vis[v]) continue;
        vis[v] = 1;
        ans1.push_back({x, v});
        ans2.push_back({tl[x], hd[v]});
        tl[x] = tl[v];
    }
}
void solve(){
    int n, u, v;
    scanf("%d", &n);
    e.resize(n + 1);
    for(int i = 1; i <= n; i++){
        e[i].clear();
        d[i] = 0;
        hd[i] = tl[i] = i;
        vis[i] = 0;
    }

    ans1.clear();
    ans2.clear();
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
        d[u]++;
        d[v]++;
    }
    for(int i = 1; i <= n; i++){
        if(d[i] == 1){
            nh = head = i;
            break;
        }
    }
    dfs(1, 0, 0);
    printf("%d\n", ans1.size());
    for(int i = 0; i < ans1.size(); i++){
        printf("%d %d %d %d\n",ans1[i].first, ans1[i].second, ans2[i].first, ans2[i].second);
    }
}
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        solve();
    }
}