#include
using namespace std;
class node
{
public:
int data;
node *left;
node *right;
node(int d)
{
data=d;
left=NULL;
right=NULL;
}
};
node * BuildBalancedTree(int *A,int s,int e)
{
if(s>e)
return NULL;
int mid=(s+e)/2;
node *root=new node(A[mid]);
root->left=BuildBalancedTree(A,s,mid-1);
root->right=BuildBalancedTree(A,mid+1,e);
return root;
}
void Preorder(node *root)
{
if(root!=NULL)
{
cout<data<<" ";
Preorder(root->left);
Preorder(root->right);
}
}
int main()
{
int t;
cin>>t;
int n;
while(t>0)
{
cin>>n;
int *A=new int[n];
for(int i=0;i<n;i++)
cin>>A[i];
node *root=BuildBalancedTree(A,0,n-1);
Preorder(root);
t–;
}
}