#include<iostream>
using namespace std;

struct TreeNode
{
    int height;   //每一个结点都要保存自己的高度
    int data;
    TreeNode* leftC;
    TreeNode* rightC;
};

//得到此时结点高度
int getHeight(TreeNode* s)
{
    if (s != NULL)
    {
        return s->height;
    }
    return -1;
}

//右旋
void rightRotate(TreeNode*& root)
{
    TreeNode *l1 = root;
    TreeNode *l2 = root->leftC;
    l1->leftC = l2->rightC;
    l2->rightC = l1;
    l1->height = (getHeight(l1->leftC) > getHeight(l1->rightC) ? getHeight(l1->leftC) : getHeight(l1->rightC)) + 1;
    l2->height = (getHeight(l2->leftC) > getHeight(l2->rightC) ? getHeight(l2->leftC) : getHeight(l2->rightC)) + 1;
    root = l2;
}

//左旋
void leftRotate(TreeNode*& root)
{
    TreeNode *l1 = root;
    TreeNode *l2 = root->rightC;
    l1->rightC = l2->leftC;
    l2->leftC = l1;
    l1->height = (getHeight(l1->leftC) > getHeight(l1->rightC) ? getHeight(l1->leftC) : getHeight(l1->rightC)) + 1;
    l2->height = (getHeight(l2->leftC) > getHeight(l2->rightC) ? getHeight(l2->leftC) : getHeight(l2->rightC)) + 1;
    root = l2;
}

//左右，先左旋，再右旋
void DoubleRotateLR(TreeNode* &n1)
{
    leftRotate(n1->leftC);
    rightRotate(n1);
}

//右左，先右旋，后左旋
void DoubleRotateRL(TreeNode* &n1)
{
    rightRotate(n1->rightC);
    leftRotate(n1);
}


void Insert(TreeNode** node, int data)
{
    if (*node == NULL)
    {
        TreeNode* tmp = new TreeNode();
        tmp->data = http://www.mamicode.com/data;" ";
    preOrder(node->leftC);
    preOrder(node->rightC);
}

void  inOrderTraversal(TreeNode* root)
{
    if(root)
    {
    	inOrderTraversal(root->leftC);
    	cout << root->data << " ";
    	inOrderTraversal(root->rightC);
    }
}

int main()
{
	int n;
	cin>>n;
	while(n-->0)
	{
	    int num;
	    cin>>num;

	    TreeNode *head=NULL;

        int point;

        for(int i=0;i<num;i++)
        {
            cin>>point;
            Insert(&head, point);
        }

        preOrder(head);
        cout<<endl;
        inOrderTraversal(head);
        cout<<endl;
    }

    return 0;
}