Give you the
in-order and post-order traversal of a binary tree **T**. Please find the preorder traversal of **T**.

Submit: 336 Solved: 196

[Submit][Status][Web Board]

Give you the
in-order and post-order traversal of a binary tree **T**. Please find the preorder traversal of **T**.

First line is an integer T, which is the number of test cases. (1 <= T <= 50)

For each test case, there will be an integer in a single line N (1 <= N <= 1024). N is the number of nodes. The nodes are numbered from 1 to N.

Then there will be two lines.

The 1^{st}/2^{nd} line will be the in/post order traversal of the Tree.

For each test case, please print the pre-order traversal of the tree.

```
1
8
7 2 4 1 5 3 8 6
7 2 4 5 8 6 3 1
```

```
1 4 2 7 3 5 6 8
```

Median problem.