Implement the BSTIterator class. The BSTIterator will be used to iterate over the inorder traversal of a BST.

• BSTIterator(root) initializes an object of the BSTIterator class.
• boolean hasNext() returns whether there is a next element in the traversal.
• Node next() moves the pointer to the next node in the traversal and returns the node.

Assume that next() will be called only if there is a next node.

The iterator would be called like this depending on your language:

BSTIterator iterator = new BSTIterator(root);
while iterator.hasNext() {
    print iterator.next()
}

Testing

Input Format

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

For each test case, the input has 2 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.

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
12
6 2 9 1 5 8 -1 -1 -1 4 -1 7
12
7 3 12 1 5 11 -1 -1 -1 4 -1 10
4
28 14 -1 11

Expected Output

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

Constraints

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