Problem: We are committed to the well being of all participants. Therefore, instead of the problem, we suggest you enjoy a piece of cake.

Uh oh. Somebody cut the cake. We told them to wait for you, but they did it anyway. There is still some left, though, if you hurry back. Of course, before you taste the cake, you thought about how the cake was cut.

It is known that the cake was originally a regular n-sided polygon, each vertex of which had a unique number from 1 to n. The vertices were numbered in random order.

Each piece of the cake is a triangle. The cake was cut into n - 2 pieces as follows: each time one cut was made with a knife (from one vertex to another) such that exactly one triangular piece was separated from the current cake, and the rest continued to be a convex polygon. In other words, each time three consecutive vertices of the polygon were selected and the corresponding triangle was cut off.

A possible process of cutting the cake is presented in the picture below.

<image> Example of 6-sided cake slicing.

You are given a set of n-2 triangular pieces in random order. The vertices of each piece are given in random order — clockwise or counterclockwise. Each piece is defined by three numbers — the numbers of the corresponding n-sided cake vertices.

For example, for the situation in the picture above, you could be given a set of pieces: [3, 6, 5], [5, 2, 4], [5, 4, 6], [6, 3, 1].

You are interested in two questions.

  * What was the enumeration of the n-sided cake vertices? 
  * In what order were the pieces cut? 



Formally, you have to find two permutations p_1, p_2, ..., p_n (1 ≤ p_i ≤ n) and q_1, q_2, ..., q_{n - 2} (1 ≤ q_i ≤ n - 2) such that if the cake vertices are numbered with the numbers p_1, p_2, ..., p_n in order clockwise or counterclockwise, then when cutting pieces of the cake in the order q_1, q_2, ..., q_{n - 2} always cuts off a triangular piece so that the remaining part forms one convex polygon.

For example, in the picture above the answer permutations could be: p=[2, 4, 6, 1, 3, 5] (or any of its cyclic shifts, or its reversal and after that any cyclic shift) and q=[2, 4, 1, 3].

Write a program that, based on the given triangular pieces, finds any suitable permutations p and q.

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Then there are t independent sets of input data.

The first line of each set consists of a single integer n (3 ≤ n ≤ 10^5) — the number of vertices in the cake.

The following n - 2 lines describe the numbers of the pieces vertices: each line consists of three different integers a, b, c (1 ≤ a, b, c ≤ n) — the numbers of the pieces vertices of cake given in random order. The pieces are given in random order.

It is guaranteed that the answer to each of the tests exists. It is also guaranteed that the sum of n for all test cases does not exceed 10^5.

Output

Print 2t lines — answers to given t test cases in the order in which they are written in the input. Each answer should consist of 2 lines.

In the first line of an answer on a test case print n distinct numbers p_1, p_2, ..., p_n(1 ≤ p_i ≤ n) — the numbers of the cake vertices in clockwise or counterclockwise order.

In the second line of an answer on a test case print n - 2 distinct numbers q_1, q_2, ..., q_{n - 2}(1 ≤ q_i ≤ n - 2) — the order of cutting pieces of the cake. The number of a piece of the cake corresponds to its number in the input.

If there are several answers, print any. It is guaranteed that the answer to each of the tests exists.

Example

Input


3
6
3 6 5
5 2 4
5 4 6
6 3 1
6
2 5 6
2 5 1
4 1 2
1 3 5
3
1 2 3


Output


1 6 4 2 5 3 
4 2 3 1 
1 4 2 6 5 3 
3 4 2 1 
1 3 2 
1 

Solution (in JAVA):

Solution:
/**
 * BaZ :D
 */
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class ACMIND
{
    static FastReader scan;
    static PrintWriter pw;
    static long MOD = 1_000_000_007 ;
    static long INF = 1_000_000_000_000_000_000L;
    static long inf = 2_000_000_000;
    public static void main(String[] args) {
        new Thread(null,null,"BaZ",1<<27)
        {
            public void run()
            {
                try
                {
                    solve();
                }
                catch(Exception e)
                {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }
    static int n, X, Y;
    static void solve() throws IOException
    {
        scan = new FastReader();
        pw = new PrintWriter(System.out,true);
        StringBuilder sb = new StringBuilder();
        int t = ni();
        while(t-->0) {
            n = ni();
            Map<Long, Integer> freq = new HashMap<>();
            Map<Long, Integer> which = new HashMap<>();
            Map<Long, Integer> which2 = new HashMap<>();
            int ans[] = new int[n-2];
            int adj[][] = new int[n+1][2];
            int a[][] = new int[n-2][3];
            for(int i=2;i<n;++i) {
                long x = ni(), y = ni(), z = ni();
                a[i-2][0] = (int)x;
                a[i-2][1] = (int)y;
                a[i-2][2] = (int)z;
                long first = get(min(x,y), max(x,y));
                add(freq, first);
                long second = get(min(y,z), max(y,z));
                add(freq, second);
                long third = get(min(x,z), max(x,z));
                add(freq, third);

                if(which.get(first) == null) {
                    which.put(first, i-2);
                }
                else {
                    which2.put(first,i-2);
                }

                if(which.get(second) == null) {
                    which.put(second, i-2);
                }
                else {
                    which2.put(second,i-2);
                }

                if(which.get(third) == null) {
                    which.put(third, i-2);
                }
                else {
                    which2.put(third,i-2);
                }
            }
            int curr_edge_freq[] = new int[n-2];
            int sx = -1, sy = -1;
            LinkedList<Integer> queue = new LinkedList<>();
            for(Map.Entry<Long, Integer> entry : freq.entrySet()) {
                if(entry.getValue() == 1) {
                    decode(entry.getKey());
                    sx = X;
                    sy = Y;
                    //pl("Edge : "+X+" "+Y);
                    if(adj[X][0] == 0) {
                        adj[X][0] = Y;
                    }
                    else {
                        adj[X][1] = Y;
                    }

                    if(adj[Y][0] == 0) {
                        adj[Y][0] = X;
                    }
                    else {
                        adj[Y][1] = X;
                    }

                    int which_triplet = which.get(entry.getKey());
                    ++curr_edge_freq[which_triplet];
                    if(curr_edge_freq[which_triplet] == 2) {
                        queue.addLast(which_triplet);
                        //pl("adding "+which_triplet);
                    }
                }
            }
//            pl();
//            pl();
            sb.append(sx);
            sb.append(" ");
            sb.append(sy);
            sb.append(" ");
            for(int i=0;i<n-2;++i) {
                int other = adj[sy][0] == sx ? adj[sy][1] : adj[sy][0];
                sx = sy;
                sy = other;
                sb.append(other);
                sb.append(" ");
            }
            sb.append("\n");
            int idx = 0;
            while(!queue.isEmpty()) {
                int x = queue.pollFirst();
                //pl("x : "+x);
                ans[idx++] = (x+1);
                long first = get(min(a[x][0], a[x][1]), max(a[x][0], a[x][1]));
                long second = get(min(a[x][1], a[x][2]), max(a[x][1], a[x][2]));
                long third = get(min(a[x][0], a[x][2]), max(a[x][0], a[x][2]));
                remove(freq, first);
                remove(freq, second);
                remove(freq, third);
                if(freq.get(first).equals(1)) {
                    int other = which.get(first) == x ? which2.get(first) : which.get(first);
                    ++curr_edge_freq[other];
                    if(curr_edge_freq[other] == 2) {
                        queue.add(other);
                        //pl("adding "+other);
                    }
                }
                if(freq.get(second).equals(1)) {
                    int other = which.get(second) == x ? which2.get(second) : which.get(second);
                    ++curr_edge_freq[other];
                    if(curr_edge_freq[other] == 2) {
                        queue.add(other);
                        //pl("adding "+other);
                    }
                }
                if(freq.get(third).equals(1)) {
                    int other = which.get(third) == x ? which2.get(third) : which.get(third);
                    ++curr_edge_freq[other];
                    if(curr_edge_freq[other] == 2) {
                        queue.add(other);
                        //pl("adding "+other);
                    }
                }
            }
            for(int e : ans) {
                sb.append(e);
                sb.append(" ");
            }
            sb.append("\n");
        }
        psb(sb);
        pw.flush();
        pw.close();
    }
    static void decode(long x) {
        Y = (int)(x%(n+1));
        X = (int)(x/(n+1));
    }
    static long get(long x, long y) {
        return x*(n+1) + y;
    }
    static void add(Map<Long, Integer> map, long key) {
        Integer val = map.get(key);
        if(val==null) {
            map.put(key, 1);
        }
        else {
            map.put(key,val+1);
        }
    }
    static void remove(Map<Long, Integer> map, long key) {
        Integer val = map.get(key);
        if(val == null) {
            return;
        }
        if(val==1) {
            map.remove(key);
        }
        map.put(key, val-1);
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[1000000];
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }
}