Given the root node of a binary search tree and a key, add the key in the tree and return the root node.

Note: The tree contains only unique values. Assume that key does not already exist in the BST.

There can be multiple solutions. You can return the root node containing any of the solutions as long as the tree is a BST.

Example

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has 3 lines:

• The first line contains an integer n denoting the number of nodes in the tree (including the NULL nodes).
• The second line contains n space-separated integers that will form the binary search tree. The integers follow level order traversal of the tree where -1 indicates a NULL node.
• The third line contains the key value to be inserted.

Output Format

For each test case, the output has a line containing the inorder traversal of the tree.

Sample Input

4
9
2 1 3 -1 -1 -1 5 4 7
8
12
6 2 9 1 5 8 -1 -1 -1 4 -1 7
3
12
7 3 12 1 5 11 -1 -1 -1 4 -1 10
2
4
28 14 -1 11
15

Expected Output

1 2 3 4 5 7 8
1 2 3 4 5 6 7 8 9
1 2 3 4 5 7 10 11 12
11 14 15 28

Constraints

1 <= T <= 10
1 <= n <= 104
1 <= node value <= 104