You are given a preorder traversal of a binary search tree, your task is to find the tree from the given preorder traversal.
For example:
You are given preOrder = [10, 5, 1, 7, 40, 50], the binary search tree from the given preorder traversal is

The first line of input contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains a single integer ‘N’ representing the size of the preorder array.
The second line of each test case contains ‘N’ space-separated integers representing the preorder traversal of the tree.
For each test, ‘N’ space-separated integers will be printed representing the inorder traversal of the tree.
Print a separate line for each test case.
Constraints:
1 <= T <= 10
1 <= N <= 10^6
1 <= preOrder[i] <= 10^9
It is guaranteed that the sum of ‘N’ over all test cases does not exceed 10^6.
Time Limit: 1 sec.
Note:
You do not need to print anything. It has already been taken care of. Just implement the function.
Sample Input 1
2
6
10 5 1 7 40 50
6
8 5 1 7 10 12
Sample Output 1:
1 5 7 10 40 50
1 5 7 8 10 12
Explanation:
For the first test case, preOrder = [10, 5, 1, 7, 40, 50], the binary search tree from the given preorder traversal is

Hence the answer is [1, 5, 7, 10, 40, 50].
For the second test case, preOrder = [8, 5, 1, 7, 10, 12], the binary search tree from the given preorder traversal is

Hence the answer is [1, 5, 7, 10, 40, 50].
Sample Input 2:
2
3
2 1 3
3
1 3 2
Sample Output 2:
1 2 3
1 2 3