import java.io.*;
import java.util.*;
class Node{
Node left,right;
int data;
Node(int data){
this.data = data;
left = null;
right = null;
}
}
public class Solution {
public static Node insert(Node root, int data){
if(root == null){
return new Node(data);
}
if(root.data > data){
root.left = insert(root.left, data);
}
else{
root.right = insert(root.right, data);
}
return root;
}
public static void Preorder(Node root){
if(root == null){
return;
}
System.out.print(root.data+" ");
Preorder(root.left);
Preorder(root.right);
}
public static void Inorder(Node root){
if(root == null){
return;
}
Inorder(root.left);
System.out.print(root.data+" ");
Inorder(root.right);
}
public static void Postorder(Node root){
if(root == null){
return;
}
Postorder(root.left);
Postorder(root.right);
System.out.print(root.data+" ");
}
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner s = new Scanner(System.in);
int t = s.nextInt();
for(int x=0;x<t;x++){
Node root = null;
int n = s.nextInt();
for(int i=0;i<n;i++){
int data = s.nextInt();
root = insert(root, data);
}
Preorder(root);
System.out.println();
Inorder(root);
System.out.println();
Postorder(root);
System.out.println();
System.out.println();
}
}
}